0

# Where dfs is used

I have seen few examples where bfs is best as below: Rotten oranges Word ladder Fire in garden Where exactly dfs is best over bfs ? Looking for pattern of problems where dfs is must.

1 Answer

+ 3

https://en.wikipedia.org/wiki/Depth-first_search#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.
- Generating words in order to plot the limit set of a group.
- Finding strongly connected components.
- Determining whether a species is closer to one species or another in a phylogenetic tree.
- 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 DFS.
- Finding biconnectivity in graphs.
- Succession to the throne shared by the Commonwealth realms."

Hot today

Python â€” File Handling

2 Votes

Help me

0 Votes

Whatâ€™s wrong?

2 Votes

Question is write a c program to print prime numbers up to n and print the largest number in array.

1 Votes

Achievements on Sololearn

1 Votes

How to draw in the console?

0 Votes