1：BFS

廣度優先搜索類似于樹的層次遍歷過程。它需要借助一個隊列來實現。如圖2-1-1所示，要想遍歷從v0到v6的每一個頂點，我們可以設v0為第一層，v1、v2、v3為第二層，v4、v5為第三層，v6為第四層，再逐個遍歷每一層的每個頂點

代碼演示

這里的代碼演示 我是將頂點的序號從 0 開始的

#include<bits/stdc++.h> using namespace std;//一些量的定義 queue<int> q; #define MaxSize 100 bool visited[100];//用于表示已經訪問過的結點 //鄰接矩陣儲存表示 typedef struct GNode* PtrGraph; typedef struct GNode{int NV;int NE;int Data[MaxSize][MaxSize]; }gnode;//創建圖 void creatGraph(PtrGraph G){int i,j;cin >> G->NV >> G->NE;//鄰接矩陣初始化for(int i = 0; i < G->NV; i++){for(int j = 0; j < G->NV; j++){G->Data[i][j] = 0;//兩點之間沒有邊相連 用 0 來表示 ，如果有邊用 1 來表示}}for(int k = 0; k < G->NE; k++){cin >> i >> j;G->Data[i][j] = 1;G->Data[j][i] = 1;//兩點之間有邊 賦值為一；} }//BFS遍歷 void BfsGraph(PtrGraph G,int a){//a = 0;//表示從0這個點開始遍歷；cout << a << ' ';//將第一個點打印出來；visited[a] = 1;//表示已經訪問過1 訪問過也就是代表已經可以遍歷了q.push(a);//將 a 入隊；while(!q.empty()){int u = q.front();q.pop();for(int i = 0; i < G->NV; i++){if(visited[i] != 1 && G->Data[u][i] !=0 ){cout << i << ' ';visited[i] = 1; //表示已經訪問過q.push(i); //將 i 入隊 }}} }// 非連通圖的BFS遍歷 void BFS_Noconnected(PtrGraph G){for(int i = 0; i < G->NV; i++){visited[i] = { 0 };//將圖中的點初始化為0}for(int i = 0; i < G->NV; i++){ // 將圖中未訪問過的結點 開始訪問if(visited[i] != 1){BfsGraph(G,i);}}}int main(){PtrGraph G;G = (PtrGraph)malloc(sizeof(struct GNode));creatGraph(G);BfsGraph(G,0);//表示要從0 開始遍歷； } //6 7 //0 1 //0 2 //0 4 //1 4 //2 5 //3 4 //3 5 //正確結果 0 1 2 4 5 3

2：DFS

深度優先搜索類似于樹的先序遍歷，具體過程如下：

準備工作：創建一個visited數組，用于記錄所有被訪問過的頂點。
1.從圖中v0出發，訪問v0。

2.找出v0的第一個未被訪問的鄰接點，訪問該頂點。以該頂點為新頂點，重復此步驟，直至剛訪問過的頂點沒有未被訪問的鄰接點為止。

3.返回前一個訪問過的仍有未被訪問鄰接點的頂點，繼續訪問該頂點的下一個未被訪問領接點。

4.重復2,3步驟，直至所有頂點均被訪問，搜索結束。

實例演示

#include<bits/stdc++.h> using namespace std;//一些量的定義 queue<int> q; #define MaxSize 100 bool visited[100];//用于表示已經訪問過的結點 //鄰接矩陣儲存表示 typedef struct GNode* PtrGraph; typedef struct GNode{int NV;int NE;int Data[MaxSize][MaxSize]; }gnode;//創建圖 void creatGraph(PtrGraph G){int i,j;cin >> G->NV >> G->NE;//鄰接矩陣初始化for(int i = 0; i < G->NV; i++){for(int j = 0; j < G->NV; j++){G->Data[i][j] = 0;//兩點之間沒有邊相連 用 0 來表示 ，如果有邊用 1 來表示}}for(int k = 0; k < G->NE; k++){cin >> i >> j;G->Data[i][j] = 1;G->Data[j][i] = 1;//兩點之間有邊 賦值為一；} }//DFS遍歷 需要用到 遞歸 因為當遍歷到一定程度 因為某個結點的鄰接點均被訪問過了 所以需要返回上一個訪問過的結點 訪問其未被訪問過的鄰接點 //（同理 若都被訪問過則再次返回） void DFS_Graph(PtrGraph G,int a){cout << a <<' '; //每次的打印就已經代表的訪問順序；visited[a] = 1;//代表已經訪問過了for( int i = 0; i < G->NV; i++){if( visited[i] != 1 && G->Data[a][i] == 1)//DFS 遍歷的專利 從一個指定的頂點出發 開始的深度遍歷 DFS_Graph(G,i);//從a的鄰接點開始遍歷}// cout << endl; }// 非連通圖的DFS遍歷 void DFS_Noconnected(PtrGraph G){for(int i = 0; i < G->NV; i++){visited[i] = { 0 };//將圖中的點初始化為0}for(int i = 0; i < G->NV; i++){ // 將圖中未訪問過的結點 開始訪問if(visited[i] != 1){DFS_Graph(G,i);}}}int main(){PtrGraph G;G = (PtrGraph)malloc(sizeof(struct GNode));creatGraph(G);DFS_Graph(G,0);//表示要從0 開始遍歷； } //6 7 //0 1 //0 2 //0 4 //1 4 //2 5 //3 4 //3 5 //遍歷順序：0 1 4 3 5 2

3：補充

如果是非聯通圖 則直接調用代碼當中的 DFS_Noconnected函數即可

4:更深入的學習

我是學了大佬的博客 在這里給大家分享出去：添加鏈接描述

總結

以上是生活随笔為你收集整理的DFS和BFS总结和代码演示（详解）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。