[グラフ/ 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を得たと仮定し、次のようにそのADJ-リスト表現は次のとおりです。

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

それは次のようになりますトンによると、その後

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

彼は擬似コードであり、π[1]はNILでなければならず、π[3]で同じでなければならない。 しかし、明らかに、π[1]は3でなければなりません。 何か不足していますか？

PS：私が疑問を提起する理由は、dfsを使用してトポロジカルソートを行っていたことです。 私の考えは次のとおりです：1.π[u]、すべての頂点の親を見つけます。2.π[u]をすべてチェックします。π[u] == 0ならば、uは0をとります。 。

Answer 1

深さ優先検索を使用してトポロジカルソートを計算する場合、DAGポイントの依存方向のエッジ（例：1はあなたの例では3に依存します）。ですから、エッジを持つDAGを提供するトポロジカルソートを行うには

は例とは逆：

このグラフを使用して

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

、あなたはトポロジカルソートを格納するための空のリストから始まる、DFSを行います。頂点vのDFSが完了した後、vがリストに追加されます。これは、ここでl格納トポロジカルソート、およびDFS-VISITのライン8後

l.append(u) 

、DFSのライン4後

l ← [] 

を添加することによって達成することができます。