DinS Written in 2017/12/8
DFS (depth-first search)
The strategy of DFS can be summarized as below:
Last chosen neighbor, first to visit.
This should remind you of stack’s LIFO. This is an implementation option, but we can also use recursive call to do DFS.
In the example below, I’ll use stack to increase understandability. This is a digraph with initial setup, the same as BFS example.
To demonstrate how DFScontrast with BFS, we’ll start from B too.
After B is chosen, we find its neighbors’ and push them into the stack.
However, we don’t visit B yet. We check up the first element in the stack, that is D, and find D’s neighbor and push them into the stack.
Again, we check up the first element in the stack and do the same thing.
But this time F doesn’t have any neighbor. If a vertex has no neighbors or all its neighbors are discovered or visited, we’ll stop here and visit F. Then pop it up.
So F is the first to be visited. Next we do the same thing: check up. This time is A. A has two neighbors. Since B is already discovered, we only push E and cut AB.
Same story again. Notice E has two neighbors. Since D is discovered, we only push G in the stack and cut ED.
Same story for G. Here G’s only neighbor F is visited, we cut GF and push nothing.
Now we check up the top element, that is G. All of G’s neighbors are done, so we visit G. Then pop it up.
Next we check up top element in the stack. That is E. all of E’s neighbor’s are visited, so we visit E and pop it up.
Same story goes for A.
Same story goes for D.
Next element is C. C has no neighbors so we visit C.
Last one is B.
The tree we get is called DFS tree. Notice the “backtrack” happened when we reached the end of vertexes.
For this particular example, DFS tree and BFS tree are the same. This is just a coincidence.
(3)Summary
For BFS, we explore the graph layer by layer. You can think of it as a conservative strategy.
For DFS, we explore the graph deep to the end and then backtrack. You can think of it as an aggressive strategy.