Does DFS visit all vertices?
An answer to this question on Stack Overflow.
Question
I just learned about DFS/BFS in my class on Python and I'm not sure I fully understand some differences. In one of the exercises afterwards, they differentiate between DFS and shortest-path DFS. Because the videos didn't really go into this, I was trying to figure it out myself and having some trouble with it.
I'm looking at a graph like this. Let's say I want to see if there's a path between 1 and 5. If I implement this without worrying about finding the shortest path, would the execution halt once it finds node 5? In other words, nodes 6-11 would never be visited. I'm pretty confident this is something I could code, but I wasn't really sure if that was no longer considered DFS.
Answer
The answer is that it depends.
For DFS, you write a function which chooses, arbitrarily, one of its children and calls itself recursively on that child. The recursive call does the same. When there are no children, you go up one level in your recursion, choose another child, and go back down.
At Node 2 in your tree, DFS doesn't know how deep either branch is and it could choose to expand either Node 3 or Node 6. If it expands Node 3, then it will never expand Node 6 because it will search everything below Node 3 before going back up to Node 2.
Similarly, if Node 1 chooses Node 8 before Node 2, then Node 11 must be explored because everything in the Node 8 branch must be explored before any other branches are explored.
(Many DFS implementations will choose the order in which they explore children in a structured way, but this is not a core component of the traversal. The key property is that once a node is chosen, every node below that node must be traversed before any other child of that node can be visited.)