reset password
Author Message
skim144
Posts: 63
Posted 21:15 Nov 09, 2014 |

If I have a directed graph with edges

A -> B

B -> C

C -> D

D -> E

and if I run DFS on node C, do I get (C, D, E)? or (C, D, E, B, A)? I'm confused. Please help!

Last edited by skim144 at 21:16 Nov 09, 2014.
yxu22
Posts: 25
Posted 21:38 Nov 09, 2014 |

You will get (C,D,E,A,B) or (C,D,E,B,A).

I added an example of DFS pseudo code below.

When you check line 5 ( the line with underline), you could see a for loop that iterates all vertex in the graph. 

So,

(C,D,E,A,B)   // if the for loop iterated vertex A after we went through C,D,E

(C,D,E,B,A)  //  if the for loop iterated vertex B after we went through C,D,E 

---------------------------------------------------

 DFS (G)
1 for each vertex u in G.V
2     u:color = WHITE
3     u:.parent = NIL
4 time = 0
5 for each vertex u in G.V
6     if u.color == WHITE
7         DFS-VISIT(G,u)


DFS-VISIT(G, u)
1 time = time + 1             // white vertex u has just been discovered
2 u.d = time
3 u.color = GRAY
4 for each v in G.Adj[u]    // explore edge (u,v)
5     if v.color == WHITE
6         v.parent = u
7         DFS-VISIT(G,v)
8 u.color = BLACK            // blacken u; it is finished
9 time = time + 1
10 u.f = time

-------------------------------------

Last edited by yxu22 at 21:40 Nov 09, 2014.
hal255
Posts: 51
Posted 21:47 Nov 09, 2014 |

I'm pretty sure it is CDEBA, but correct me if I'm wrong:

"C is my starting point"

"C points to D, which points to E"

then it traces back,

"does D connect to anything that's unvisited?" -- no

"Does C connect to anything that's not visited?" -- no

"B is next cuz it points to C"

"Does B point to anything else?" -- no

"A is next cuz it points to B"

"Does A point to anything else?" -- no

done

skim144
Posts: 63
Posted 21:51 Nov 09, 2014 |

Thanks for clarifying.

I ran into this question because on the code provided on wiki, if I try this graph with edges I provide, I get (C, D, E).

 

hal255
Posts: 51
Posted 22:05 Nov 09, 2014 |

Nevermind, there is a nested loop. It just doesn't go from n to 1.

Oh, it's because in the normal algorithm (the nested loop), we traverse through the entire list from n to 1. If explored, we move to the next one. But the earlier code has a start node, but no nested loops to traverse through n to 1.

So it goes from start node, to wherever is the far end until it can't go any further, without tracing back.

Last edited by hal255 at 22:10 Nov 09, 2014.
vsluong4
Posts: 87
Posted 23:01 Nov 09, 2014 |

A DFS will get you (C, D, E)

 

A DFS-loop will get you (C, D, E), then (A, B)

Or (C, D, E), then (B), and finally (A)

It really depends which node the loop gets to after it's done exploring everything it can starting from C

 

The important thing to take away from this is that a DFS (and a BFS for that matter) will get to everything reachable from the start node and nothing else

This is the point of the first-pass DFS; we need the proper search order of the nodes so a search will only visit 'sink' SCCs.   Why it accomplishes this, you'll have to watch and understand the proof of Karasuja's algorithm.

Last edited by vsluong4 at 23:18 Nov 09, 2014.