拓樸排序是怎麼排序的？

方法：1、找到圖中的一個入度為0的結點，將此節點從圖中剔除並加入到序列E中；2、將1中找到的結點的全部關聯的邊從圖中去掉；3、重複1,2直到圖中的全部結點被去除或無法找到入度為0的結點為止。

本教學操作環境：windows7系統、Dell G3電腦。

1. 找到圖中的一個入度為0的結點，將此節點從圖中剔除並加入到序列E中

2. 將1中找到的結點的全部關聯的邊從圖中去掉

3. 重複1,2直到圖中的全部結點被去除或無法找到入度為0的結點為止

若此時圖中的結點數為0則找到了拓樸序列，若此時圖中結點數不為0說明圖中存在環，無法進行拓樸排序。

擴充資料：

對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓樸排序，是將G中所有頂點排成一個線性序列，使得圖中任一對頂點u和v，若邊∈E(G)，則u在線性序列中出現在v之前。通常，這樣的線性序列稱為滿足拓樸次序(Topological Order)的序列，簡稱拓樸序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個運算稱之為拓樸排序。

執行步驟

由AOV網路建構拓樸序列的拓樸排序演算法主要是循環執行以下兩步，直到不存在入度為0的頂點。

(1) 選擇一個入度為0的頂點並輸出之；

(2) 從網中刪除此頂點及所有出邊。

循環結束後，若輸出的頂點數小於網路中的頂點數，則輸出「有迴路」訊息，否則輸出的頂點序列就是一種拓樸序列。

更多電腦相關知識，請造訪常見問題欄位！

以上是拓樸排序是怎麼排序的？的詳細內容。更多資訊請關注PHP中文網其他相關文章！