圖 - 拓撲排序 （一）

　　拓撲排序(Topological Sort)

　　對一個 有向無環圖 (Directed Acyclic Graph簡稱 DAG )G進行拓撲排序是將G中所有頂點排成一個線性序列使得圖中任

　　意一對頂點u和v若 ∈E(G)則u在線性序列中出現在v之前

　　通常這樣的線性序列稱為滿足拓撲次序(TopoiSicai Order)的序列簡稱 拓撲序列

　　注意

　　①若將圖中頂點按拓撲次序排成一行則圖中所有的有向邊均是從左指向右的

　　②若圖中存在有向環則不可能使頂點滿足拓撲次序

　　③一個DAG的拓撲序列通常表示某種方案切實可行

　　【例】一本書的作者將書本中的各章節學習作為頂點各章節的先學後修關系作為邊構成一個有向圖按有向圖的拓撲次序安

　　排章節才能保證讀者在學習某章節時其預備知識已在前面的章節裡介紹過

　　④一個DAG可能有多個拓撲序列

　　【例】對圖G 進行拓撲排序至少可得到如下的兩個(實際遠不止兩個)拓撲序列C C C C C C C

　　 C C 和C C C C C C C C C

　　

　　⑤當有向圖中存在有向環時拓撲序列不存在

　　【例】下面(a)圖中的有向環重排後如(b)所示有向邊和其它邊反向若有向圖被用來表示某項工程實施方案或某項

　　工作計劃則找不到該圖的拓撲序列(即含有向環)就意味著該方案或計劃是不可行的

　　

　　無前趨的頂點優先的拓撲排序方法

　　該方法的每一步總是輸出當前無前趨(即人度為零)的頂點其抽象算法可描述為

　　NonPreFirstTopSort(G){//優先輸出無前趨的頂點

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

　　從G中選擇一個人度為的頂點v且輸出之;

　　從G中刪去v及其所有出邊;

　　}

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

　　//若此條件不成立則表示所有頂點均已輸出排序成功

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

　　}

　　對G執行上述算法的執行過程和得到的拓撲序列是C C C C C C C C C

　　注意

　　無前趨的頂點優先的拓撲排序算法在具體存儲結構下為便於考察每個頂點的人度可保存各頂點當前的人度為避免每次選入

　　度為的頂點時掃描整個存儲空間可設一個棧或隊列暫存所有入度為零的頂點

　　在開始排序前掃描對應的存儲空間將人度為零的頂點均入棧(隊)以後每次選人度為零的頂點時只需做出棧(隊)操作即可

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