拓撲排序找出給定一個特定節點

enter image description here

我可以使用什麼算法，輸出與任務拓撲有序列表來完成，這是相關的只爲特定節點？

例如，考慮到node 2，名單應該是：

7, 5, 11, 2

或

5, 7, 11, 2

來源

2013-01-22 Elad Benda

所以，你不關心節點的順序？在這種情況下，你實際上不需要拓撲排序。 – svick

我不明白。要求輸出所有節點還是隻有部分？ –

@svick不關心其他節點 –

反向邊緣
運行DFS從2
開始在離開一個結點，其插入到列表中。

例子：

Enter 2 
    Enter 11 
    Enter 7 
    Leave 7, insert into list 
    Enter 5 
    Leave 5, insert into list 
    Leave 11, insert into list 
Done, insert 2 into list 

Result: 7, 5, 11, 2

來源

2013-01-22 14:29:28 phant0m

您必須將圖形分解爲鄰接矩陣，其中從節點A的每一個環節到節點B在節點對應於節點和列的矩陣中被表示爲「1」。

從這一點開始，您需要做的就是從終端節點向後工作，識別指向它的節點，然後從每個節點向後工作。

現在，您可能希望以寬度優先的方式執行此操作，因此請使用隊列數據結構來跟蹤「依賴」節點。

來源

2013-01-22 12:53:27

我不認爲這個答案的第一句話是正確的 - 拓撲排序（及其變體）不需要創建一個鄰接矩陣。這可能是一種方法，但這不是一個必要的步驟。 –

@HighPerformanceMark儘管這就是問題所在，但拓撲排序實際上並不是問題的要求。 – svick

回答這個問題並不需要建立一個鄰接矩陣，儘管它可能是一個有用的步驟。 –

拓撲排序找出給定一個特定節點

回答

相關問題