CODEWITHSUNDEEP
graph-theorytopological-sort
Alcott
Alcott

Reputation: 18585

[graph/DFS]: problem about dfs in DAG

Here is the pseudo-code copied from "intro to algorithm" for your convenience:

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

Here is my question: Suppose I got a DAG, its adj-list representation is as follows:

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

It should look like this:

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

then according to the pseudo-code, π[1] should be NIL, and the same for π[3]. but apparently, π[1] should be 3, right? Am I missing something?

PS: the reason why I pose the question is that, I was doing the topological sorting using dfs. And my thought is: 1.find every vertex's parent, namely π[u], 2.check every π[u], if π[u]==0, then u has 0 indegree, and put u in the ordered list.

Upvotes: 0

Views: 851

Answers (1)

David Alber
David Alber

Reputation: 18111

For computing a topological sort using depth-first search, edges in the DAG point in the direction of dependency (e.g., 1 depends on 3 in your example).

So to do the topological sort you would provide a DAG with edges reversed from the example:

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

Using this graph, you do the DFS, starting with an empty list for storing the topological sort. After DFS is completed for vertex v, v is appended to the list. This could be accomplished by adding

l ← []

after line 4 of DFS, where l stores the topological sort, and

l.append(u)

after line 8 of DFS-VISIT.

Upvotes: 1

Related Questions