Graphs data structure: DFS vs BFS?

GraphGraph Theory

Graph Problem Overview

if given a graph problem how do we know whether we need to use bfs or dfs algorithm??? or when do we use dfs algorithm or bfs algorithm. What are the differences and advantages of one over other?

Graph Solutions

Solution 1 - Graph

BFS is going to use more memory depending on the branching factor... however, BFS is a complete algorithm... meaning if you are using it to search for something in the lowest depth possible, BFS will give you the optimal solution. BFS space complexity is O(b^d)... the branching factor raised to the depth (can be A LOT of memory).

DFS on the other hand, is much better about space however it may find a suboptimal solution. Meaning, if you are just searching for a path from one vertex to another, you may find the suboptimal solution (and stop there) before you find the real shortest path. DFS space complexity is O(|V|)... meaning that the most memory it can take up is the longest possible path.

They have the same time complexity.

In terms of implementation, BFS is usually implemented with Queue, while DFS uses a Stack.

Solution 2 - Graph

breadth first searches for siblings first. depth first obviously searches for children first. So, I guess it would depend on what kind of searching you're looking to do. relationship type searches across fields would probably lend itself to bfs, where hierarchical (trees, folders, ranks, etc) would be more suited as a dfs.

Solution 3 - Graph

Both the graph traversals promise one thing: a complete traversal of the graph, visiting every vertex in the graph. If you have memory constraints, DFS is a good choice, as BFS takes up a lot of space. So, choosing between these two depends on your requirement.

Want to find the (strongly/)connected components of the graph? Or solve the maze? Or sudoku? Use DFS. If you look closely, the Pre-Order, Post-Order and In-Order are all variants of the DFS. So, yes, that's some interesting applications.

BFS if you want to test if a graph is bipartite, find the shortest path between two nodes or applications that require such tasks.

Solution 4 - Graph

In bfs queue is used while in dfs stack is used to store vertices according to graph traversal.
2- in bfs process is done level to level (according to directed or non directed graph) while in dfs the process is done to depth (the process of first visiting the root node and another is do far and then apply backtracking from last node to root node).


All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionJonyView Question on Stackoverflow
Solution 1 - GraphPolaris878View Answer on Stackoverflow
Solution 2 - GraphdhossView Answer on Stackoverflow
Solution 3 - GraphmadCodeView Answer on Stackoverflow
Solution 4 - Graphanshu shrivastavsView Answer on Stackoverflow