Are there any graph-problems that can be solved by DFS or BFS, but not the other? That is, does a graph-problem exist that is solvable by BFS, but not DFS, or vice-versa?
3 Answers
BFS but not DFS: unweighted shortest paths.
DFS but not BFS: lots of algorithms due to Tarjan, e.g., strongly connected components and biconnected components.
The simplest example is: find the minimal number of edges you must traverse to get from vertex A
to vertex B
in a given graph. This can be solved easily with BFS, but not with DFS. Finding the simple cycles in a graph, however is usually solved using DFS.
Yes: here is one such problem that can be solved by BFS but not DFS:
GAME RULES
- Board is 3x3 grid
- Player one can choose any available space and put an X
- Player two can choose any available space and put an O
- Game ends when either player has three like symbols in a row
- Game ends if no spaces are available
- Players may choose to skip their turn
PROBLEM
Search to see if it is possible for this game to ever end.
BFS APPROACH
- Try all 1-ply games
- Try all 2-ply games
- ...
- Try all 9-ply games (one of these is the solution)
DFS APPROACH
- Try all games that start with player one skipping their turn
- Try all games that start with above and then player two skipping their turn
- Try all games that start with above and then player one skipping their turn
- ...
- Heat death of the universe