拓撲排序介紹 拓撲排序(Topological Order)是指，將一個有向無環圖(Directed Acyclic Graph簡稱DAG)進行排序進而得到一個有序的線性序列。 這樣說，可能理解起來比較抽象。下面通過簡單的例子進行說明！ 例如，一個項目包括A、B、C、D四個子部分來完成，並且A依賴於B和D，C依賴於D。現在要制定一個計劃，寫出A、B、C、D的執行順序。這時，就可以利用到拓撲排序，它就是用來確定事物發生的順序的。 在拓撲排序中，如果存在一條從頂點A到頂點B的路徑，那麼在排序結果中B出現在A的後面。 拓撲排序的算法圖解 拓撲排序算法的基本步驟： 1. 構造一個隊列Q(queue) 和 拓撲排序的結果隊列T(topological)； 2. 把所有沒有依賴頂點的節點放入Q； 3. 當Q還有頂點的時候，執行下面步驟： 3.1 從Q中取出一個頂點n(將n從Q中刪掉)，並放入T(將n加入到結果集中)； 3.2 對n每一個鄰接點m(n是起點，m是終點)； 3.2.1 去掉邊<n,m>; 3.2.2 如果m沒有依賴頂點，則把m放入Q; 注：頂點A沒有依賴頂點，是指不存在以A為終點的邊。 以上圖為例，來對拓撲排序進行演示。 第1步：將B和C加入到排序結果中。 頂點B和頂點C都是沒有依賴頂點，因此將C和C加入到結果集T中。假設ABCDEFG按順序存儲，因此先訪問B，再訪問C。訪問B之後，去掉邊<B,A>和<B,D>，並將A和D加入到隊列Q中。同樣的，去掉邊<C,F>和<C,G>，並將F和G加入到Q中。 (01) 將B加入到排序結果中，然後去掉邊<B,A>和<B,D>；此時，由於A和D沒有依賴頂點，因此並將A和D加入到隊列Q中。 (02) 將C加入到排序結果中，然後去掉邊<C,F>和<C,G>；此時，由於F有依賴頂點D，G有依賴頂點A，因此不對F和G進行處理。 第2步：將A,D依次加入到排序結果中。 第1步訪問之後，A,D都是沒有依賴頂點的，根據存儲順序，先訪問A，然後訪問D。訪問之後，刪除頂點A和頂點D的出邊。 第3步：將E,F,G依次加入到排序結果中。 因此訪問順序是：B -> C -> A -> D -> E -> F -> G 拓撲排序的代碼說明 拓撲排序是對有向無向圖的排序。下面以鄰接表實現的有向圖來對拓撲排序進行說明。 1. 基本定義 復制代碼 #define MAX 100 // 鄰接表 class ListDG { private: // 內部類 // 鄰接表中表對應的鏈表的頂點 class ENode { int ivex; // 該邊所指向的頂點的位置 ENode *nextEdge; // 指向下一條弧的指針 friend class ListDG; }; // 鄰接表中表的頂點 class VNode { char data; // 頂點信息 ENode *firstEdge; // 指向第一條依附該頂點的弧 friend class ListDG; }; private: // 私有成員 int mVexNum; // 圖的頂點的數目 int mEdgNum; // 圖的邊的數目 VNode *mVexs; // 圖的頂點數組 public: // 創建鄰接表對應的圖(自己輸入) ListDG(); // 創建鄰接表對應的圖(用已提供的數據) ListDG(char vexs[], int vlen, char edges[][2], int elen); ~ListDG(); // 深度優先搜索遍歷圖 void DFS(); // 廣度優先搜索（類似於樹的層次遍歷） void BFS(); // 打印鄰接表圖 void print(); // 拓撲排序 int topologicalSort(); private: // 讀取一個輸入字符 char readChar(); // 返回ch的位置 int getPosition(char ch); // 深度優先搜索遍歷圖的遞歸實現 void DFS(int i, int *visited); // 將node節點鏈接到list的最後 void linkLast(ENode *list, ENode *node); }; 復制代碼 (01) ListDG是鄰接表對應的結構體。 mVexNum是頂點數，mEdgNum是邊數；mVexs則是保存頂點信息的一維數組。 (02) VNode是鄰接表頂點對應的結構體。 data是頂點所包含的數據，而firstEdge是該頂點所包含鏈表的表頭指針。 (03) ENode是鄰接表頂點所包含的鏈表的節點對應的結構體。 ivex是該節點所對應的頂點在vexs中的索引，而nextEdge是指向下一個節點的。 2. 拓撲排序 復制代碼 /* * 拓撲排序 * * 返回值： * -1 -- 失敗(由於內存不足等原因導致) * 0 -- 成功排序，並輸入結果 * 1 -- 失敗(該有向圖是有環的) */ int ListDG::topologicalSort() { int i,j; int index = 0; int head = 0; // 輔助隊列的頭 int rear = 0; // 輔助隊列的尾 int *queue; // 輔組隊列 int *ins; // 入度數組 char *tops; // 拓撲排序結果數組，記錄每個節點的排序後的序號。 ENode *node; ins = new int[mVexNum]; queue = new int[mVexNum]; tops = new char[mVexNum]; memset(ins, 0, mVexNum*sizeof(int)); memset(queue, 0, mVexNum*sizeof(int)); memset(tops, 0, mVexNum*sizeof(char)); // 統計每個頂點的入度數 for(i = 0; i < mVexNum; i++) { node = mVexs[i].firstEdge; while (node != NULL) { ins[node->ivex]++; node = node->nextEdge; } } // 將所有入度為0的頂點入隊列 for(i = 0; i < mVexNum; i ++) if(ins[i] == 0) queue[rear++] = i; // 入隊列 while (head != rear) // 隊列非空 { j = queue[head++]; // 出隊列。j是頂點的序號 tops[index++] = mVexs[j].data; // 將該頂點添加到tops中，tops是排序結果 node = mVexs[j].firstEdge; // 獲取以該頂點為起點的出邊隊列 // 將與"node"關聯的節點的入度減1； // 若減1之後，該節點的入度為0；則將該節點添加到隊列中。 while(node != NULL) { // 將節點(序號為node->ivex)的入度減1。 ins[node->ivex]--; // 若節點的入度為0，則將其"入隊列" if( ins[node->ivex] == 0) queue[rear++] = node->ivex; // 入隊列 node = node->nextEdge; } } if(index != mVexNum) { cout << "Graph has a cycle" << endl; delete queue; delete ins; delete tops; return 1; } // 打印拓撲排序結果 cout << "== TopSort: "; for(i = 0; i < mVexNum; i ++) cout << tops[i] << " "; cout << endl; delete queue; delete ins; delete tops; return 0; } 復制代碼 說明： (01) queue的作用就是用來存儲沒有依賴頂點的頂點。它與前面所說的Q相對應。 (02) tops的作用就是用來存儲排序結果。它與前面所說的T相對應。
