[圖/ DFS]：問題關於DAG

Question

這裏的DFS是僞代碼「介紹到算法」爲了您的方便複製：

DFS(G) 
1 for each vertex u ∈ V [G] 
2  do color[u] ← WHITE //color changes from WHITE,GRAY,BLACK 
3   π[u] ← NIL   //π[u] stands for the parent of vertex u 
4 time ← 0 
5 for each vertex u ∈ V [G] 
6  do if color[u] = WHITE 
7    then DFS-VISIT(u) 

DFS-VISIT(u) 
1 color[u] ← GRAY  ▹White vertex u has just been discovered. 
2 time ← time +1 
3 d[u] time   //d[u] is the time when u is entered 
4 for each v ∈ Adj[u] ▹Explore edge(u, v). 
5  do if color[v] = WHITE 
6    then π[v] ← u 
7       DFS-VISIT(v) 
8 color[u] BLACK  ▹ Blacken u; it is finished. 
9 f [u] ▹ time ← time +1 //f[u] is the time when u is exited 

這裏是我的問題： 假設我有一個DAG，它的形容詞列表表示如下：

1:2, 4 
2:5 
3:1 
4: 
5: 

它應該是這樣的：

3 ---> 1 ---> 2 ---> 5 
     |---> 4 

然後根據t3他的僞代碼，π[1]應該是NIL，並且對於π[3]是一樣的。 但顯然，π[1]應該是3，對嗎？ 我錯過了什麼嗎？

PS：我提出這個問題的原因是，我在做使用dfs的拓撲排序。 我的想法是：1.找到每個頂點的父項，即π[u]，2.檢查每個π[u]，如果π[u] == 0，則u有0個indegree，並將u放入有序列表中。

Answer 1

爲了使用深度優先搜索來計算拓撲排序，DAG中的邊指向相關性的方向（例如，1取決於您的示例中的3）。

所以，我們要做的拓撲排序，你會提供一個DAG從例如扭轉邊緣：

1: 3 
2: 1 
3: 
4: 1 
5: 2 

使用這個圖，你做的DFS，開始用於存儲拓撲排序列表爲空。在頂點v的DFS完成後，將v附加到列表中。這可以通過管線4的DFS，之後加入

l ← [] 

來實現，其中l存儲的拓撲排序和

l.append(u) 

的DFS-VISIT管線8後。