拓撲排序

????對于一個有向無環圖，我們可以這樣確定一個圖中頂點的順序：?
對于所有的u、v，若存在有向路徑u-->v，則在最后的頂點排序中u就位于v之前。這樣確定的順序就是一個圖的拓撲排序。?
????拓撲排序的特點：?
（1）所有可以到達頂點v的頂點u都位于頂點v之前；?
（2）所有從頂點v可以到達的頂點u都位于頂點v之后；?
（3）只有有向無環圖才存在拓撲排序；?
（4）一個圖的拓撲順序不唯一

實現拓撲排序

思路?
????圖中入度為0的點沒有任何點可以到達它，因此可以排在最開始（若有多個入度為0的點，他們之間的相對順序隨意）；?
????因為入度為0的頂點已經排完序了，因此可以將那些入度為0的頂點去掉。去掉之后的圖中，還會存在一些入度為0的頂點，因此可以繼續采用上述的方法....?
????到最后圖中還有一些入度均不為0的頂點，那么在這個圖中從任意一個頂點開始走下去，必然會經過每個頂點多于1次，即存在環，與前提矛盾！

實現?
????拓撲排序常用的算法是通過一個隊列存放入度為0的點，每次取出隊列頭元素，訪問該頂點，然后然后將該點連接的所有邊消除，再將新圖的入度為0的點加入隊列...直到圖中不存在入度為0的點。

#define MAX_NODE 1000 #define MAX_EDGE_NUM 100000 struct Edge{int to;int w;int next; }; Edge gEdges[MAX_EDGE_NUM]; int gHead[MAX_NODE]; bool gVisited[MAX_NODE]; int gInDegree[MAX_NODE]; int gEdgeCount; void InsertEdge(int u, int v, int w){int e = gEdgeCount++;gEdges[e].to = v;gEdges[e].w = w;gEdges[e].next = gHead[u];gHead[u] = e;gInDegree[v] ++; //入度加1 } void TopoSort(int n /*節點數目*/){queue<int> zero_indegree_queue;for (int i = 0; i < n; i++){
　　　　　　　　if (gInDegree[i] == 0)zero_indegree_queue.push(i);}memset(gVisited, false, sizeof(gVisited));while (!zero_indegree_queue.empty()){int u = zero_indegree_queue.front();zero_indegree_queue.pop();gVisited[u] = true;//輸出ufor (int e = gHead[u]; e != -1; e = gEdges[e].next){int v = gEdges[e].to;gInDegree[v] --;if (gInDegree[v] == 0){zero_indegree_queue.push(v);}}}for (int i = 0; i < n; i++){if (!gVisited[i]){//存在環！ 無法形成拓撲序}} }

?

總結

以上是生活随笔為你收集整理的有向无环图的拓扑排序的全部內容，希望文章能夠幫你解決所遇到的問題。

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