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.

2nd Nov 2022, 8:11 AM
Ketan Lalcheta
Ketan Lalcheta - avatar
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."
2nd Nov 2022, 2:22 PM
Tibor Santa
Tibor Santa - avatar