Depth-first Search - Applications

Applications

Algorithms that use depth-first search as a building block include:

  • Finding connected components.
  • Topological sorting.
  • Finding 2-(edge or vertex)-connected components.
  • Finding 3-(edge or vertex)-connected components.
  • Finding the bridges of a graph.
  • Finding strongly connected components.
  • Planarity testing
  • Solving puzzles with only one solution, such as mazes. (DFS can be adapted to find all solutions to a maze by only including nodes on the current path in the visited set.)
  • Maze generation may use a randomized depth-first search.
  • Finding biconnectivity in graphs.

Read more about this topic:  Depth-first Search