CODEWITHSUNDEEP
searchgraphtreedepth-first-searchdepth
antekkalafior
antekkalafior

Reputation: 282

Depth-first search how it decides to visit node

Imagine we have a graph like this:

enter image description here

The DFS would search it in the order of the digits in the picture.

I wonder how it knows when to pick 6 over 8.

I know it searches for the deepest part first but how does it know whether to go for 6 or 8 when the algorithm doesn't know what lies beyond nodes 6 and 8

Upvotes: 1

Views: 574

Answers (1)

bob tang
bob tang

Reputation: 593

the answer to whether to go for 6 or 8 is simply based on the implementation of the your DFS and the structure of your graph. But no matter it goes to node 6 first or node 8 first, both are the correct implementation of DFS.

let's take a look at this DFS Pseudocode (recursive implementation) as an example:

DFS(G, u)
u.visited = true
for each v ∈ G.Adj[u]
    if v.visited == false
        DFS(G,v)

so which line of code decides the next adjacent node to go first(pick node 6 or node 8 in your case)? It is the 3rd line

 for each v ∈ G.Adj[u]

and we know that the "for loop" could have different sequences of iterating the adjacent nodes. someone could also implement it as

for(int i=0; i<G.Adj[u].length; i++)

or

for(int i=G.Adj[u].length-1; i>=0; i--)

And these two "for loop" are totally different sequences of picking the next adjacent node. And also the arraylist of G.Adj[u] could be different from case to case (based on how your initialize the graph). if the "for loop" gets the node 6 first, it keeps searching down the node 6, otherwise it searches the node 8. Once again, no matter it picks 6 or 8, both are correct implementation of DFS.

Upvotes: 1

Related Questions