[图形/ dfs ]：关于DAG中的dfs的问题

Question

为了方便起见，下面是从“算法简介”中复制的伪代码：

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，它的adj-list表示如下：

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

它应该看起来像这样：

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

然后根据伪代码，π1应该是零，π3也是如此。但是显然，π1应该是3，对吧？我是不是遗漏了什么？

PS:我提出这个问题的原因是，我正在使用dfs进行拓扑排序。我的想法是:1.找到每个顶点的父节点，即πu，2.检查每个顶点u，如果是πu==0，则u有0个π，并将u放在有序列表中。

Answer 1

对于使用深度优先搜索计算拓扑排序，DAG中的边指向依存关系的方向(例如，在您的示例中，1取决于3)。

因此，要进行拓扑排序，您需要提供一个DAG，其中包含与示例相反的边：

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

使用此图，您可以执行DFS，从一个用于存储拓扑排序的空列表开始。顶点v的DFS完成后，将v追加到列表中。这可以通过添加

l ← []

在DFS的第4行之后，其中l存储拓扑排序，以及

l.append(u)

在DFS-VISIT的第8行之后。