Graphs data structure: DFS vs BFS?

graph graph-theory
Jony picture Jony · Apr 13, 2010 · Viewed 74.9k times · Source

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?

Answer

Polaris878 picture Polaris878 · Apr 13, 2010

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.

Related questions

Cycles in an Undirected Graph

Given an undirected graph G=(V, E) with n vertices (|V| = n), how do you find if it contains a cycle in O(n)?

Read More
Difference between hamiltonian path and euler path

Can some one tell me the difference between hamiltonian path and euler path. They seem similar!

Read More
What is the distinction between sparse and dense graphs?

I read it is ideal to represent sparse graphs by adjacency lists and dense graphs by an adjacency matrix. But I would like to understand the main difference between sparse and dense graphs.

Read More