Graphs data structure: DFS vs BFS?

Question

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?

Solution 1

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

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

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

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).

View more solutions

Comments

[Polaris878]

The time complexity for both is: O(b^d)... meaning it is based on the branching factor and the depth searched. BFS and DFS have the same worst case... searching the entire tree.

[DogEatDog]

Here is a good link for commentary on when you might use either of them. programmerinterview.com/index.php/data-structures/dfs-vs-bfs

[Rocky]

The book (introduction to algorithms) says the time complexity of BFS is O(V+E), but DFS is θ(V+E). Why is that?

[Faizan]

@Rocky you got your answer, if so then share it with us.

[Sebastian Graf]

Re O vs Theta: It should be Theta for BFS too (which doesn't make the statement contradictory), because every node is initially colored white and we must respect Theta(E) edges. Re space complexity: Both DFS and BFS execute in linear space, but DFS doesn't hit the worst case that often. If it does, the visited node set (colors in Cormen) is ommitted and algorithms such as IDDFS can be used, which don't need linear space (or at least can allocate adaptively).

[Shital Shah]

Answer is not correct about memory usage. Both can consume worse case O(V) memory. Worse case for BFS is one parent with n child while the worse case for DFS is chain of n nodes with one child per parent. So depending on graph topology, BFS or DFS both have equal chance of winning.

[Mohammad Mahdi KouchakYazdi]

No , they don't have the same time complexity. BFS: O(b^d) , DFS: O(b^m) . where m is the longest path.