數據結構之拓撲排序

概念

　　有向無環圖（Directed Acyclic Graph）:一個無環的有向圖簡稱DAG圖
　　拓撲排序（Topological Sort）將一個有向無環圖G中所有頂點排成一個線性序列使得對圖中任意一對頂點u和v若＜uv＞∈E(G)則u在線性序列中出現在v之前
　　拓撲序列將一個有向無環圖進行拓撲排序得到的線性序列稱為滿足拓撲次序（Topological Order）的序列
拓撲排序是對於有向無環圖才可以排序成功的若圖中存在有向環則該拓撲序列不存在

拓撲排序兩種方法

　　無前趨的頂點優先
　　步驟
　　() 在有向圖中選一個沒有前驅的頂點且輸出之
　　() 從圖中刪除該頂點且刪除以它為尾的所有弧
　　() 重復上述兩步直至全部頂點均已輸出或者圖中不存在無前驅的頂點為止後一種情況則說明有向圖中存在環
　
　　無後繼的頂點優先

　　根據這個算法每一步輸出的是當前無後繼(出度為)的頂點要將其序列逆序後才是拓撲序列可以用一個棧來保存輸出結果
　　當采用DFS算法進行拓撲排序時若給定的圖是一個非DAG也就是圖中存在有向環時它不能正常工作這是因為在DFS遍歷中凡訪問過的結點均不會再次被訪問因此這個算法將忽略圖中的有向環的存在從而造成錯誤在前其它算法中若存在有向環則輸出結點數總小於頂點總數因此能夠被發現

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