CODEWITHSUNDEEP
algorithmgraphgraph-theorygraph-algorithm
The Big Cheese
The Big Cheese

Reputation: 81

Depth-First Search vs. Breadth-First Search

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?

Upvotes: 0

Views: 724

Answers (3)

William Entriken
William Entriken

Reputation: 39323

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

Upvotes: 1

David Eisenstat
David Eisenstat

Reputation: 65506

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.

Upvotes: 4

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 71009

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.

Upvotes: 2

Related Questions