Imagine we have a graph like this:
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
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.