Apply Depth-first Search Algorithm Example

  • Topic:
  • Thread starter evinda
  • Start date
  • Tags Tags
    Search
4 replies · 2K views · last reply
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Wave)

I want to apply the algorithm of the depth-first search at an example.

Code:
Depthfirstsearch(G)
   for each v ∈ V
        color[v]<-white
        p[v]<-Ø
   time<-Ø
   for each u ∈ V
       if color[u]=white then
          Visit(u)

Code:
Visit(u)
  color[u]<-gray
  time<-time+1
  d[u]<-time
  for each v ∈ Adj[u]
       if color[v]=white then
          p[v]<-u
          Visit(v)
  color[u]<-black
  time<-time+1
  f[u]<-time

This is the example,at which I want to apply the algorithm:

View attachment 3064

According to my notes,it is like that:

View attachment 3066

but..I found the following:

View attachment 3067

Could you tell me which of them is right? Have I done something wrong? (Thinking)
 
Attachments
  • Directed graph with vertices a, b, c, g, h and i; edges a to b, a to g, g to b, b to h, c to h and c to i, plus a self-loop on i.
    gra.png
    3.2 KB · Views: 165
  • Directed graph with vertices a, b, c, g, h and i, labelled with discovery and finishing times in red: a (1, 2), b (2, 3), c (7, 10), g (5, 6), h (3, 4), i (8, 9).
    gra.png
    3.5 KB · Views: 167
  • Directed graph with vertices a, b, c, g, h and i, black and gray vertices with red discovery and finish times labelled beside them, showing a depth-first search traversal.
    gra.png
    3.6 KB · Views: 141
The book's solution is alphabetical, i.e. starts at node "A" and then proceeds to "B". Yours went from "A" to "G".

I don't think it really matters? It shouldn't if you've got the principle of it. I glanced at your code and it looks fine to me.
 
jza said:
The book's solution is alphabetical, i.e. starts at node "A" and then proceeds to "B". Yours went from "A" to "G".

I don't think it really matters? It shouldn't if you've got the principle of it. I glanced at your code and it looks fine to me.

I think I have done some mistakes.. (Wasntme) I tried it again now.

After $a$,I started again with the node $g$ and now I got:

View attachment 3077

Could you tell me if it is right now? (Thinking)
 
Attachments
  • Directed graph with nodes a, b, c, g, h, i; red numbers beside each node show a depth-first search order, with arrows a to b, a to g, g to b, b to h, c to h, c to i, and a self-loop on i.
    gra.png
    3.5 KB · Views: 159
evinda said:
I think I have done some mistakes.. (Wasntme) I tried it again now.

After $a$,I started again with the node $g$ and now I got:

https://www.physicsforums.com/attachments/3077

Could you tell me if it is right now? (Thinking)

Hey evinda! ;)

I believe you are right.
The final state is where all nodes are black.

The algorithm works by initializing all nodes to white.
Then each of those nodes is visited and traced to its neighbors.
When a node is visited, it is set to gray, and when all neighbors have been visited, it is set to black.
When all nodes have been visited, they are all black. (Smile)

I believe the state in your notes cannot occur.
Since $g$ is black, it has been visited.
This implies that all of its neighbors have also been visited and should also be black. But $b$ is not black. :eek:
 
I like Serena said:
Hey evinda! ;)

I believe you are right.
The final state is where all nodes are black.

The algorithm works by initializing all nodes to white.
Then each of those nodes is visited and traced to its neighbors.
When a node is visited, it is set to gray, and when all neighbors have been visited, it is set to black.
When all nodes have been visited, they are all black. (Smile)

I believe the state in your notes cannot occur.
Since $g$ is black, it has been visited.
This implies that all of its neighbors have also been visited and should also be black. But $b$ is not black. :eek:

Great!Thank you very much! (Smirk)