代碼如下:

/* 鄰接表存儲 - 拓撲排序算法 */bool TopSort( LGraph Graph, Vertex TopOrder[] ) { /* 對Graph進行拓撲排序, TopOrder[]順序存儲排序后的頂點下標 */int Indegree[MaxVertexNum], cnt;Vertex V;PtrToAdjVNode W;Queue Q = CreateQueue( Graph->Nv );/* 初始化Indegree[] */for (V=0; V<Graph->Nv; V++)Indegree[V] = 0;/* 遍歷圖，得到Indegree[] */for (V=0; V<Graph->Nv; V++)for (W=Graph->G[V].FirstEdge; W; W=W->Next)Indegree[W->AdjV]++; /* 對有向邊<V, W->AdjV>累計終點的入度 *//* 將所有入度為0的頂點入列 */for (V=0; V<Graph->Nv; V++)if ( Indegree[V]==0 )AddQ(Q, V);/* 下面進入拓撲排序 */ cnt = 0; while( !IsEmpty(Q) ){V = DeleteQ(Q); /* 彈出一個入度為0的頂點 */TopOrder[cnt++] = V; /* 將之存為結果序列的下一個元素 *//* 對V的每個鄰接點W->AdjV */for ( W=Graph->G[V].FirstEdge; W; W=W->Next )if ( --Indegree[W->AdjV] == 0 )/* 若刪除V使得W->AdjV入度為0 */AddQ(Q, W->AdjV); /* 則該頂點入列 */ } /* while結束*/if ( cnt != Graph->Nv )return false; /* 說明圖中有回路, 返回不成功標志 */ elsereturn true; }

總結

以上是生活随笔為你收集整理的拓扑排序(C语言)的全部內容，希望文章能夠幫你解決所遇到的問題。

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