數據結構之圖的遍歷

圖的遍歷

圖的遍歷目的是訪問圖的每一個頂點恰好一次,，同時訪問圖中每條邊恰好一 次。

對于無向圖，常見的遍歷方式有深度優先遍歷（Depth-First Search, DFS） 和廣度優先遍歷（Breadth-First Search, BFS）。

1 深度優先遍歷（DFS）

深度優先遍歷是一種用于遍歷或搜索樹或圖的算法。

深度優先搜索是一個遞歸的過程。

  • 首先，選定一個出發點后進行遍歷，如果有鄰接的未被訪問過的節點則繼續前進。
  • 若不能繼續前進，則回退一步再前進
  • 若回退一步仍然不能前進，則連續回退至可以前進的位置為止。
  • 重復此過程，直到所有與選定點相通的所有頂點都被遍歷。

示例

先選擇一個起始的頂點

、在這里插入圖片描述

選擇其中一個鄰接點

在這里插入圖片描述

3沒有鄰接點，回退到2

在這里插入圖片描述

2有兩個鄰接點，但是3已經訪問過了，選擇0

在這里插入圖片描述

0有兩個鄰接點，但是2已經訪問過了，選擇1

在這里插入圖片描述

1有1個鄰接點，但是2已經訪問過了,于是整個深度優先遍歷完成，輸出結果為2->3->0->1

代碼如下：

#include <iostream>
using namespace std;// 定義圖的邊（頂點值默認從0開始）用兩個頂點之間的連接表示邊
typedef struct Node
{int vertex;        // 下一個頂點的值struct Node *next; // 下一條頂點（如果當前頂點沒有更多的鄰接點，則此指針為NULL）
} Node;// 定義圖
typedef struct Graph
{int numVertices; // 頂點數Node **adjLists; // 鄰接表，指向指針數組的指針，每個指針都指向一個Node鏈表的頭部。數組// 的大小numVertices 數組元素則是指向從該頂點出發的第一條邊的指針（如果頂點沒有鄰接點，則為// NULL）。bool *isVisited; // 標記看看是不是訪問過 數組的大小numVertices （頂點數）
}Graph;// 創建一個圖，包含vertices個頂點
Graph *createGraph(int vertices)
{Graph *graph = new Graph();if (!graph){perror("創建失敗");return nullptr;}// /初始化頂點數graph->numVertices = 0;graph->adjLists = new Node *[vertices]; // 表示一個包含 vertices 個 Node* 元素的數組。在C++中，數組名在大多數情況下會退化成指向數組首元素的指針// new Node*[vertices] 返回的是一個指向包含 vertices 個 Node* 元素的數組的指針，其類型是 Node**，這與 adjLists 的類型匹配// /為鄰接表申請內存for (int i = 0; i < vertices; ++i){graph->adjLists[i] = nullptr;}// 標注位申請內存graph->isVisited = new bool [vertices] { 0 };return graph;
}// 添加邊 src起點 dest終點
void addEdge(Graph *graph, int src, int dest)
{// 創建邊Node *newNode = new Node();//  //設置鄰接點newNode->vertex = dest;// 將新邊添加到起點的鏈表中newNode->next = graph->adjLists[src];// 更新第一天條邊graph->adjLists[src] = newNode;graph->adjLists[src] = newNode;如果是無向圖，也需要添加反向邊Node* newNode2 = (Node*)malloc(sizeof(Node));// Node* newNode2 = new Node;// newNode2->vertex = src;// newNode2->link = graph->adjLists[dest];// graph->adjLists[dest] = newNode2;
}// 深度優先遍歷
void DFS(Graph *graph, int v)
{// 輸出遍歷到的節點cout << v << " ";// 遞歸訪問所有未訪問的鄰接頂點Node *adjList = graph->adjLists[v];while (adjList){// 標記當前節點為已訪問graph->isVisited[v] = true;// 鄰接點未被訪問到if (!graph->isVisited[adjList->vertex]){ // 遞歸調用 訪問他的所有鄰接點DFS(graph, adjList->vertex);}// 往后遍歷每一條邊adjList = adjList->next;}
}// 清理Graph對象
void freeGraph(Graph *graph)
{if (!graph){return;}// 釋放鄰接表中每個鏈表占用的內存for (int i = 0; i < graph->numVertices; ++i){Node *current = graph->adjLists[i];while (current){Node *next = current->next; // 保存下一條邊的指針delete current;             // 釋放當前邊的內存current = next;             // 移動到下一條邊}}// 釋放鄰接表數組本身占用的內存delete[] graph->adjLists;// 釋放訪問標記數組占用的內存delete[] graph->isVisited;
}int main()
{// 創建一個包含4個頂點的圖Graph *graph = createGraph(4);addEdge(graph, 0, 1);addEdge(graph, 0, 2);addEdge(graph, 1, 2);addEdge(graph, 2, 0);addEdge(graph, 2, 3);// 深度優先遍歷圖cout << "深度優先遍歷（從頂點2開始）:" << endl;DFS(graph, 2);delete graph;graph = NULL;return 0;
}

newNode1->next = graph->adjList[src];意思是 新節點的 next 指針指向當前 src 鄰接鏈表的第一個節點。

這樣，新節點 newNode1 被插入到鏈表的頭部

graph->adjList[src] = newNode1; 將 src 的鄰接鏈表的頭部更新為 newNode1。這樣，newNode1 成為鏈表的新頭節點

結果是

深度優先遍歷（從頂點2開始）:
2 0 1 3

1.2 廣度優先遍歷（BFS）

廣度優先遍歷是圖的另一種遍歷方式，它從根節點開始，首先訪問離根節點最近的節點（即根節點的所 有鄰接節點），然后逐層向外訪問，直到訪問完所有節點。

  • 從圖中某頂點v出發，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點
  • 然后分別從這些鄰接點出發依次訪問它們的鄰接點，并使得“先被訪問的頂點的鄰接點先于后被訪問的頂點的鄰接點被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。
  • 如果此時圖中尚有頂點未被訪問，則需要另選一個未曾被訪問過的頂點作為新的起始點，重復上述過程，直至圖中所有頂點都被訪問到為止(隊列為空)。

示例

先選擇一個起始的頂點·

在這里插入圖片描述

2的鄰接點有兩個，全部入隊，隊列元素為3， 0

在這里插入圖片描述

3沒有鄰接點，出列，輸出3,隊列元素為0

在這里插入圖片描述

0的鄰接點是1和2，但是2已經訪問過了，1入隊，0出列，輸出0，隊列元素為1

在這里插入圖片描述

1的鄰接點是2，但是2已經訪問過了，0出列，輸出0，隊列元素為空，同時訪問完畢 整個廣度優先遍歷完成，輸出結果為2->3->0->1

在這里插入圖片描述

代碼如下

#include <iostream>
using namespace std;
#include <queue>
// 定義圖的邊（頂點值默認從0開始）用兩個頂點之間的連接表示邊
typedef struct Node
{int vertex;        // 下一個頂點的值struct Node *next; // 下一條頂點（如果當前頂點沒有更多的鄰接點，則此指針為NULL）
} Node;// 定義圖
typedef struct Graph
{int numVertices; // 頂點數Node **adjLists; // 鄰接表，指向指針數組的指針，每個指針都指向一個Node鏈表的頭部。數組// 的大小numVertices 數組元素則是指向從該頂點出發的第一條邊的指針（如果頂點沒有鄰接點，則為// NULL）。bool *isVisited; // 標記看看是不是訪問過 數組的大小numVertices （頂點數）
}Graph;// 創建一個圖，包含vertices個頂點
Graph *createGraph(int vertices)
{Graph *graph = new Graph();if (!graph){perror("創建失敗");return nullptr;}// /初始化頂點數graph->numVertices = vertices;graph->adjLists = new Node *[vertices]; // 表示一個包含 vertices 個 Node* 元素的數組。在C++中，數組名在大多數情況下會退化成指向數組首元素的指針// new Node*[vertices] 返回的是一個指向包含 vertices 個 Node* 元素的數組的指針，其類型是 Node**，這與 adjLists 的類型匹配// /為鄰接表申請內存for (int i = 0; i < vertices; ++i){graph->adjLists[i] = nullptr;}// 標注位申請內存graph->isVisited = new bool [vertices] { 0 };return graph;
}// 添加邊 src起點 dest終點
void addEdge(Graph *graph, int src, int dest)
{// 創建邊Node *newNode = new Node();//  //設置鄰接點newNode->vertex = dest;// 將新邊添加到起點的鏈表中newNode->next = graph->adjLists[src];// 更新第一天條邊graph->adjLists[src] = newNode;如果是無向圖，也需要添加反向邊Node* newNode2 = (Node*)malloc(sizeof(Node));// Node* newNode2 = new Node;// newNode2->vertex = src;// newNode2->link = graph->adjLists[dest];// graph->adjLists[dest] = newNode2;
}// 深度優先遍歷
void DFS(Graph *graph, int v)
{// 輸出遍歷到的節點cout << v << " ";// 遞歸訪問所有未訪問的鄰接頂點// 第一個頂點Node *adjList = graph->adjLists[v];// 標記當前節點為已訪問graph->isVisited[v] = true;while (adjList){// 鄰接點未被訪問到if (!graph->isVisited[adjList->vertex]){ // 遞歸調用 訪問他的所有鄰接點DFS(graph, adjList->vertex);}// 往后遍歷每一條邊adjList = adjList->next;}
}// 廣度優先遍歷 
void BFS(Graph* graph, int startVertex)
{// 初始化隊列  queue <int> q;// / 標記所有頂點為未訪問for(int i = 0; i < graph->numVertices ; ++i){graph->isVisited[i] = false;}      // 將起始頂點加入隊列，并標記為已訪問      q.push(startVertex);graph->isVisited[startVertex] = true;// 循環條件是隊列不為空while (!q.empty()){// 從隊列中取出第一個頂點int  vertex = q.front(); //出隊    q.pop();// 訪問該頂點 cout <<  "Visited " << vertex << endl;// 遍歷訪問的頂點的所有鄰接點 Node* current  = graph->adjLists[vertex];while (current){ //鄰接點 終點int adjVertex = current->vertex;// 如果鄰接點未被訪問，則加入隊列并標記為已訪問if(!graph->isVisited[adjVertex])  {q.push(adjVertex);graph->isVisited[adjVertex] = true;}// 移動到下一個鄰接點 current = current->next;}}
}
// 清理Graph對象
void freeGraph(Graph *graph)
{if (!graph){return;}// 釋放鄰接表中每個鏈表占用的內存for (int i = 0; i < graph->numVertices; ++i){Node *current = graph->adjLists[i];while (current){Node *next = current->next; // 保存下一條邊的指針delete current;             // 釋放當前邊的內存current = next;             // 移動到下一條邊}}// 釋放鄰接表數組本身占用的內存delete[] graph->adjLists;// 釋放訪問標記數組占用的內存delete[] graph->isVisited;
}int main()
{// 創建一個包含4個頂點的圖Graph *graph = createGraph(4);addEdge(graph, 0, 1);addEdge(graph, 0, 2);addEdge(graph, 1, 2);addEdge(graph, 2, 3);addEdge(graph, 2, 0);// 深度優先遍歷圖cout << "深度優先遍歷（從頂點2開始）:" << endl;DFS(graph, 2);cout << endl;cout << "廣度優先遍歷（從頂點2開始）:" << endl;BFS(graph, 2);delete graph;graph = NULL;return 0;
}

  • 問題1：初始化的時候把頂點numVertices 初始化為0了而且創建時候沒有再賦值，直接初始化傳入節點就行了

  • 問題2 graph->isVisited[v] = true; 放在循環外面，那么下面訪問了之后會再標記嗎

    當然會，這是遞歸，會調用自己

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/904990.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/904990.shtml
英文地址，請注明出處：http://en.pswp.cn/news/904990.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Ubuntu 第11章 網絡管理_常用的網絡配置命令

Ubuntu 第11章 網絡管理_常用的網絡配置命令

為了管理網絡&#xff0c;Linux提供了許多非常有用的網絡管理命令。利用這些命令&#xff0c;一方面可以有效地管理網絡&#xff0c;另一方面出現網絡故障時&#xff0c;可以快速進行診斷。本節將對Ubuntu提供的網絡管理命令進行介紹。 11.2.1 ifconfig命令 關于ifconfig命令&…
閱讀更多...
Qt解決自定義窗口樣式不生效問題

Qt解決自定義窗口樣式不生效問題

方法一&#xff1a; this->setAttribute(Qt::WA_StyledBackground, true); 方法二&#xff1a; 將類繼承QWidget 改成繼承 QFrame class MyWidget : public QFrame {} 方法三&#xff1a;重新實現QWidget的paintEvent函數時&#xff0c;使用QStylePainter繪制。 void p…
閱讀更多...
HNUST湖南科技大學-軟件測試期中復習考點（保命版）

HNUST湖南科技大學-軟件測試期中復習考點（保命版）

使用說明&#xff1a;本復習考點僅用于及格保命。軟件測試和其他專業課不太一樣&#xff0c;記憶的太多了&#xff0c;只能說考試的時候&#xff0c;想到啥就寫啥&#xff0c;多寫一點&#xff01;多寫一點&#xff01;多寫一點&#xff01;&#xff08;重要事情說三遍&#xf…
閱讀更多...
ES6 知識點整理

ES6 知識點整理

一、變量聲明&#xff1a;var、let、const 的區別 作用域 var&#xff1a;函數作用域&#xff08;函數內有效&#xff09;。let/const&#xff1a;塊級作用域&#xff08;{} 內有效&#xff0c;如 if、for&#xff09;。 變量提升 var 會提升變量到作用域頂部&#xff08;值為…
閱讀更多...
分布式爬蟲去重：Python + Redis實現高效URL去重

分布式爬蟲去重：Python + Redis實現高效URL去重

1. 引言 在互聯網數據采集&#xff08;爬蟲&#xff09;過程中&#xff0c;URL去重是一個關鍵問題。如果不對URL進行去重&#xff0c;爬蟲可能會重復抓取相同頁面&#xff0c;導致資源浪費、數據冗余&#xff0c;甚至觸發目標網站的反爬機制。 對于單機爬蟲&#xff0c;可以使…
閱讀更多...
C# WPF 顏色拾取器

C# WPF 顏色拾取器

x:Name=Color Picker 語言：C# WPF 下載：https://download.csdn.net/download/polloo2012/90780640 主界面 顏色庫 關于我們 顏色拾取器是一種能夠幫助用戶獲取顏色信息，并進行顏色選擇、識別和調整的工具，以下將從其常見類型、使用場景及部分軟件工具這幾個維度展開介紹…
閱讀更多...
Git 使用的全流程以及SourceTree工具的使用操作和忽略文件的配置

Git 使用的全流程以及SourceTree工具的使用操作和忽略文件的配置

1. 安裝 Git 要使用 Git&#xff0c;首先得在你的系統上安裝它。你可以按照不同操作系統的安裝指南來操作&#xff1a; Windows&#xff1a;訪問 Git 官方下載頁面&#xff0c;下載安裝程序并運行。 macOS&#xff1a;可以使用 Homebrew 來安裝&#xff0c;命令為 brew inst…
閱讀更多...
《深入理解Linux網絡》筆記

《深入理解Linux網絡》筆記

《深入理解Linux網絡》筆記 前言參考 前言 前段時間看了《深入理解Linux網絡》這本書&#xff0c;雖然有些地方有以代碼充篇幅的嫌疑&#xff0c;但總體來說還是值得一看的。在這里簡單記錄一下筆記&#xff0c;記錄下對網絡新的理解。 內核是如果接受網絡包的&#xff1f; 如…
閱讀更多...
數倉-可累計，半累加，不可累加指標，是什么，舉例說明及解決方案

數倉-可累計，半累加，不可累加指標，是什么，舉例說明及解決方案

目錄 1. 可累計指標定義&#xff1a;舉例&#xff1a;解決方案&#xff1a; 2. 半累加指標定義&#xff1a;舉例&#xff1a;解決方案&#xff1a; 3. 不可累加指標定義&#xff1a;舉例&#xff1a;解決方案&#xff1a; 4. 總結對比5. 實際場景中的注意事項 這是數據倉庫設計…
閱讀更多...
NestJS 的核心構建塊有哪些？請簡要描述它們的作用（例如，Modules, Controllers, Providers）

NestJS 的核心構建塊有哪些？請簡要描述它們的作用（例如，Modules, Controllers, Providers）

NestJS 核心構建塊解析&#xff08;Modules、Controllers、Providers&#xff09; NestJS 是一個基于 TypeScript 的漸進式 Node.js 框架&#xff0c;核心設計借鑒了 Angular 的模塊化思想。下面從實際開發角度解析它的三大核心構建塊&#xff0c;并附代碼示例和避坑指南。 一…
閱讀更多...
vue2 上傳pdf，拖拽蓋章，下載圖片

vue2 上傳pdf，拖拽蓋章，下載圖片

效果圖片&#xff1a; 不多廢話上代碼&#xff1a; <template><div class"pdf-stamp" onbeforecopyreturn false onselectdocument.selection.empty() ondragstartreturn false onselectstart return false ><div class"scroll-box" scro…
閱讀更多...
理性地傾聽與表達：檢索算法的語言學改進

理性地傾聽與表達：檢索算法的語言學改進

論文標題 Rational Retrieval Acts: Leveraging Pragmatic Reasoning to Improve Sparse Retrieval 論文地址 https://arxiv.org/pdf/2505.03676 代碼地址 https://github.com/arthur-75/Rational-Retrieval-Acts 作者背景 巴黎薩克雷大學&#xff0c;索邦大學&#xff…
閱讀更多...
MySQL及線程關于鎖的面試題

MySQL及線程關于鎖的面試題

目錄 1.了解過 MySQL 死鎖問題嗎&#xff1f; 2.什么是線程死鎖&#xff1f;死鎖相關面試題 2.1 什么是死鎖&#xff1a; 2.2 形成死鎖的四個必要條件是什么&#xff1f; 2.3 如何避免線程死鎖&#xff1f; 3. MySQL 怎么排查死鎖問題&#xff1f; 4.Java線上死鎖問題如…
閱讀更多...
【Reality Capture 】Reality Capture1.5中文版安裝教程（附安裝包下載）

【Reality Capture 】Reality Capture1.5中文版安裝教程（附安裝包下載）

文章目錄 一、Reality Capture1.5中文版安裝教程二、拷貝中文補丁三、Reality Capture1.5中文版下載地址一、Reality Capture1.5中文版安裝教程 1. Reality Capture v1.4.0漢化版安裝包下載并解壓 2. 運行EpicInstaller-15.17.1-4a91a118786f4c2aa3c0093b23f83863.msi 3. 更改…
閱讀更多...
SVG數據可視化設計（AI）完全工作流解讀｜計育韜

SVG數據可視化設計（AI）完全工作流解讀｜計育韜

AI 的 SVG 創作極限在哪里&#xff1f;絕不是那些初級的流程圖生成和粗糙的商業模型設計。以下是由我們 JZ Creative Studio 通過 Claude 和 Deepseek 開展的專業級 SVG Data Visualization 創作&#xff0c;應廣大讀者強烈要求&#xff0c;專程直播講授了一期 AI 工作流分享。…
閱讀更多...
not a genuine st device abort connection的問題

not a genuine st device abort connection的問題

1.魔法棒里面電機Settings 2.然后在Other里面把Enabled的鉤子去掉
閱讀更多...
uv簡單使用

uv簡單使用

通過uv創建項目和虛擬環境 初始化項目 uv init --package my-project 初始化一個名為 my-project 的新項目&#xff0c;并生成必要的文件結構。 創建虛擬環境 uv venv .venv 激活虛擬環境 # For Windows .venv\Scripts\activate# For macOS/Linux source .venv/bin/acti…
閱讀更多...
測試左移系列-產品經理實戰-實戰認知1

測試左移系列-產品經理實戰-實戰認知1

課程&#xff1a;B站大學 記錄產品經理實戰項目系統性學習&#xff0c;從產品思維&#xff0c;用戶畫像&#xff0c;用戶體驗&#xff0c;增長數據驅動等不同方向理解產品&#xff0c;從0到1去理解產品從需求到落地的全過程&#xff0c;測試左移方向&#xff08;靠近需求、設計…
閱讀更多...
從需求到用例的AI路徑：準確率與挑戰

從需求到用例的AI路徑：準確率與挑戰

用工作流生成測試用例和自動化測試腳本&#xff01; 引言&#xff1a;用例的黃金起點 在軟件工程中&#xff0c;“測試用例”是連接需求理解與質量保障之間的關鍵橋梁。一份高質量的測試用例&#xff0c;不僅是驗證功能實現是否符合需求的工具&#xff0c;更是產品風險感知、用…
閱讀更多...
大語言模型中的“溫度”參數到底是什么？如何正確設置？

大語言模型中的“溫度”參數到底是什么？如何正確設置？

近年來&#xff0c;市面上涌現了大量調用大模型的工具&#xff0c;如 Dify、Cherry Studio 等開源或自研平臺&#xff0c;幾乎都提供了 “溫度”&#xff08;Temperature&#xff09; 選項。然而&#xff0c;很多人在使用時并不清楚該如何選擇合適的溫度值。 今天&#xff0c;…
閱讀更多...
最新文章

Copyright @ 2022~2023