[图/ 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后。