鄰接表存儲的圖 - DFS

/* 鄰接表存儲的圖 - DFS */void Visit( Vertex V ) {printf("正在訪問頂點%d\n", V); }/* Visited[]為全局變量，已經初始化為false */ void DFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) ) { /* 以V為出發點對鄰接表存儲的圖Graph進行DFS搜索 */PtrToAdjVNode W;Visit( V ); /* 訪問第V個頂點 */Visited[V] = true; /* 標記V已訪問 */for( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 對V的每個鄰接點W->AdjV */if ( !Visited[W->AdjV] ) /* 若W->AdjV未被訪問 */DFS( Graph, W->AdjV, Visit ); /* 則遞歸訪問之 */ }

鄰接矩陣存儲的圖 - BFS：

/* 鄰接矩陣存儲的圖 - BFS *//* IsEdge(Graph, V, W)檢查<V, W>是否圖Graph中的一條邊，即W是否V的鄰接點。 */ /* 此函數根據圖的不同類型要做不同的實現，關鍵取決于對不存在的邊的表示方法。*/ /* 例如對有權圖, 如果不存在的邊被初始化為INFINITY, 則函數實現如下: */ bool IsEdge( MGraph Graph, Vertex V, Vertex W ) {return Graph->G[V][W]<INFINITY ? true : false; }/* Visited[]為全局變量，已經初始化為false */ void BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) ) { /* 以S為出發點對鄰接矩陣存儲的圖Graph進行BFS搜索 */Queue Q; Vertex V, W;Q = CreateQueue( MaxSize ); /* 創建空隊列, MaxSize為外部定義的常數 *//* 訪問頂點S：此處可根據具體訪問需要改寫 */Visit( S );Visited[S] = true; /* 標記S已訪問 */AddQ(Q, S); /* S入隊列 */while ( !IsEmpty(Q) ) {V = DeleteQ(Q); /* 彈出V */for( W=0; W<Graph->Nv; W++ ) /* 對圖中的每個頂點W *//* 若W是V的鄰接點并且未訪問過 */if ( !Visited[W] && IsEdge(Graph, V, W) ) {/* 訪問頂點W */Visit( W );Visited[W] = true; /* 標記W已訪問 */AddQ(Q, W); /* W入隊列 */}} /* while結束*/ }

總結

以上是生活随笔為你收集整理的图的遍历(C语言,邻接表存储的图 - DFS,邻接矩阵存储的图 - BFS)的全部內容，希望文章能夠幫你解決所遇到的問題。

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