0

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?

2
  • Perfectly legitimate question with a possible answer and related to programming Commented Apr 16, 2014 at 19:38
  • It's more computer-science than programming. Commented Apr 16, 2014 at 20:22

3 Answers 3

4

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.

2

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.

1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.