圖的遍歷

圖的遍歷是指從圖中的某一頂點出發，按照某種搜索方式沿著途中的邊對圖中所有頂點訪問一次且僅訪問一次。圖的遍歷主要有兩種算法：廣度優先搜索和深度優先搜索。

廣度優先遍歷BFS

廣度優先遍歷（BFS 也叫廣度優先搜索）類似于二叉樹的層序遍歷算法

#define MaxSize 100; bool visited[MaxSize]； //訪問數組，記錄頂點是否被訪問過，初始都賦值為false void BFS(Graph G,int v){ //圖用鄰接表存儲，從下標為v的位置開始遍歷ArcNode *p; //工作指針pInitQueue(Q); //初始化一個隊列visit(v); //訪問第一個頂點v 具體可以是Print visited[v]=TRUE; //對v做已訪問標記Enqueue(Q,v); //頂點v入隊列while(!isEmpty(Q)){ //只要隊列不空DeQueue(Q,v); //頂點v出隊列p=G->adjList[v].firstedge; //指針p指向當前頂點的邊表鏈表頭指針while(p){ if(!visited[p->adjvex]){ //p所指向頂點如果未被訪問 visit(p->adjvex); //訪問p所指向的頂點visited[p->adjvex]=TRUE; //對這個頂點做已訪問標記EnQueue(Q,p->adjvex); //這個頂點入隊列} p=p->next； //p指向該頂點的下一條邊}} } void BFSTraverse(Graph G){int i; //單獨定義是為了方便多個循環中使用for(i=0; i<G->vexnum; i++）visited[i]=false; //將標志數組初始化 (全局數組)for(i=0; i<G->vexnum; i++){ if(!visited[i])BFS(G,i);} //為了避免非連通圖一些頂點訪問不到 若是連通圖只會執行一次} }

BFS復雜度分析

不論是鄰接表還是鄰接矩陣的存儲方式，BFS算法都需要借助一個輔助隊列Q，n個頂點均需入隊一次，在最壞的情況下，空間復雜度為$O(|V|)$。

當采用鄰接表存儲方式時，每個頂點均需要搜索一次（或者入隊一次）姑時間復雜度為$O(|V|)$，在搜索任意一頂點的臨接點時，每條邊需要訪問一次，故時間復雜度為$O(|E|)$。算法的總時間復雜度為$O(|V|+|E|)$。

當采用鄰接矩陣存儲方式時，查找每個頂點的臨接點所需的時間為$O(|V|)$，故算法的時間復雜度為$O(|V{|}^2)$。

BFS應用

BFS解決單源非帶權圖最短路徑問題：按照距離由近到遠來遍歷圖中每個頂點

void BFS_MIN_Distance(Graph G,int u){ //d[i]表示從u到i結點的最短路徑for(i=0;i<G.vexnum;++i) d[i]=∞; //初始化路徑長度visited[u]=TRUE; d[u]=0;EnQueue(Q,u);while(!isEmpty(Q)){ DeQueue(Q,u); ArcNode *p=G->adjList[u].firstedge; while(p){ If(!visited[p->adjvex]){ visited[p->adjvex]=TRUE; //路徑長度加1 d[p->adjvex]=d[u]+1; EnQueue(Q, p->adjvex); } p=p->next；}} }

廣度優先生成樹

深度優先遍歷DFS

深度優先遍歷(DFS:Depth-First-Search):深度優先遍歷類似于樹的先序遍歷算法
首先訪問圖中某一起始頂點v，然后由v出發，訪問與v鄰接且未被訪問的任一頂點w1，再訪問與w1鄰接且未被訪問的任一頂點w2，……重復上述過程。當不能再繼續向下訪問時，依次退回到最近被訪問的頂點，若它還有鄰接頂點未被訪問過，則從該點開始繼續上述搜索過程，直到圖中所有頂點均被訪問過為止

#define MaxSize 100; bool visited[MaxSize]； void DFS(Graph G,int v){ArcNode *p; //工作指針pvisit(v); //訪問頂點v(一般是打印，即printf)visited[v]=TRUE; //修改訪問標記p=G->adjlist[v].firstarc; //指針p開始指向該頂點的第一條邊while(p!=NULL){ //沒遍歷完頂點的所有鄰接頂點if(!visited[p->adjvex]){ //如果該頂點沒被訪問DFS(G,p->adjvex); //遞歸訪問該頂點} p=p->nextarc; //看還有沒有其他未訪問的頂點 } void DFSTraverse(Graph G){int i; //單獨定義是為了方便多個循環中使用for(i=0; i<G->vexnum; i++）visited[i]=false; //將標志數組初始化 (全局數組)for(i=0; i<G->vexnum; i++){ if(!visited[i]) DFS(G,i); //對所有 }

DFS算法是一個遞歸算法，需要借助一個遞歸工作棧，故她的空間復雜度為$O(|V|)$。
遍歷圖的過程實質上是對每個頂點查找其臨接點的過程，其耗費的時間取決于所采用的存儲結構。

當以鄰接表表示時，查找所有頂點的臨接點所需時間為$O(|E|)$，訪問頂點所需時間為$O(V)$，此時，總的時間復雜度為$O(|V|+|E|)$。

當以鄰接矩陣進行表示時，查找每個頂點的鄰接點所需時間為$O(|V|)$，故總的時間復雜度為$O(|V{|}^2)$。

深度優先生成樹

參考資料

王道數據結構

總結

以上是生活随笔為你收集整理的【数据结构】图的遍历（BFS和DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

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