圖 - 拓撲排序 （二）

　　無後繼的頂點優先拓撲排序方法

　　思想方法

　　該方法的每一步均是輸出當前無後繼(即出度為)的頂點對於一個DAG按此方法輸出的序列是 逆拓撲次序 因此設置一個

　　棧(或向量)T來保存輸出的頂點序列即可得到拓撲序列若T是棧則每當輸出頂點時只需做人棧操作排序完成時將棧中頂點依

　　次出棧即可得拓撲序列若T是向量則將輸出的頂點從T[n]開始依次從後往前存放即可保證T中存儲的頂點是拓撲序列

　　抽象算法描述

　　算法的抽象描述為

　　NonSuccFirstTopSort(G){//優先輸出無後繼的頂點

　　while(G中有出度為的頂點)do {

　　從G中選一出度為的頂點v且輸出v;

　　從G中刪去v及v的所有人邊

　　}

　　if(輸出的頂點數目<|V(G)|)

　　Error(G中存在有向環排序失敗!);

　　}

　　算法求精

　　在對該算法求精時可用逆鄰接表作為G的存儲結構設置一個向量outdegree[n]或在逆鄰接表的頂點表結點中增加個出

　　度域來保存各頂點當前的出度;設置一個棧或隊列來暫存所有出度為零的頂點除了增加一個棧或向量T來保存輸出的頂點序列外

　　該算法完全類似於NonPreFirstTopSort具體算法【參見練習】

　　利用深度優先遍歷對DAG拓撲排序

　　當從某頂點v出發的DFS搜索完成時v的所有後繼必定均已被訪問過(想像它們均已被刪除)此時的v相當於是無後繼的頂點因

　　此在DFS算法返回之前輸出頂點v即可得到 DAG的逆拓撲序列

　　其中第一個輸出的頂點必是無後繼(出度為)的頂點它應是拓撲序列的最後一個頂點若希望得到的不是逆拓撲序列同樣可增

　　加T來保存輸出的頂點若假設T是棧並在DFSTraverse算法的開始處將T初始化

　　利用DFS求拓撲序列的抽象算法可描述為

　　void DFSTopSort(GiT){

　　//在DisTraverse中調用此算法i是搜索的出發點T是棧

　　int j;

　　visited[i]=TRUE; //訪問i

　　for(所有i的鄰接點j)//即∈E(G)

　　if(!visited[j])

　　DFSTopSort(GjT);

　　//以上語句完全類似於DFS算法

　　Push(&Ti); //從i出發的搜索已完成輸出i

　　}

　　只要將深度優先遍歷算法DFSTraverse中對DFS的調用改為對DFSTopSort的調用即可求得拓撲序列T其具體算法不難從上述抽

　　象算法求精後得到

　　若G是一個DAG則用DFS遍歷實現的拓撲排序與NonSuccFirstTopSort算法完全類似;但若C中存在有向環則前者不能正常工作

From:http://tw.wingwit.com/Article/program/sjjg/201311/23812.html