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)
------------------------------------- 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.
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.
|