Apply Depth-first Search Algorithm Example

[evinda]

Hello! (Wave)

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

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

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)

 

[jza]

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.

 

[evinda]

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)

 

[I like Serena]

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.

 

[evinda]

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.

Great!Thank you very much! (Smirk)