通過圓弧進行拓撲排序

Question

確實只需要一些指導： 通過圓弧定義的拓撲排序（從我的問題） - 是對方向圖中的所有圓弧進行排序的一種方式，因此插入到頂點的所有圓弧必須先於從這個頂點出來。

Answer 1

無需在拓撲排序中改變任何東西，你可以使用它和後期處理。

高電平僞代碼：

1. 運行拓撲排序，讓所得到的數組是arr
2. 創建空邊緣列表中，讓它成爲l
在 arr [有序迭代]
3. 爲每個頂點v ：
   3.1。對於每個(v,u) in E：
   3.1.1。追加(v,u) to l
4. 回報l

這種方法的好處是，你可以使用拓撲排序爲黑盒，而無需修改它，只是後期處理，以獲得所需的結果。

正確性 [證明的草圖]：
由於每個邊緣(v,u) - u顯示在拓撲排序v後，在打印它，它是通過v完成，並且因此(v,u)打印任何頂點之前被印刷附於u。

複雜：
O(|V|+|E|)拓撲排序，O(|V|+|E|)用於後處理[迭代的所有頂點和所有邊緣。

Answer 2

「傳統」拓撲排序是對頂點進行排序，而這是對弧進行排序。否則，原理是一樣的...