DAG和Top Sort

Question

「根據增加的預編號排列DAG的頂點會導致拓撲排序。」顯然不是一個真實的陳述，但我不明白爲什麼它不是。如果圖是有向的並且沒有周期，那麼我們訪問頂點的順序不應該是我們對拓撲進行排序的正確順序嗎？

Answer 1

通過增加預編號進行排列並不能保證有效的拓撲排序。考慮一下這個圖表：

A 
    ↓ 
B → C → D 

該圖表的兩個有效拓撲順序是：

A, B, C, D 
B, A, C, D 

如果你訪問節點與Ç，一個可能的預先編號的順序將是開始：

C, D, A, B 

這不是一個有效的拓撲順序。一個更簡單的例子是這樣的曲線圖：

B → A 

顯然有一個有效的拓撲排序，但如果我們參觀一個第一和排序前數，產生的順序將是倒退。