Advantage of depth first search over breadth first search or vice versa

algorithm graph graph-algorithm
Kris picture Kris · May 15, 2012 · Viewed 21.6k times · Source

I have studied the two graph traversal algorithms,depth first search and breadth first search.Since both algorithms are used to solve the same problem of graph traversal I would like to know how to choose between the two.I mean is one more efficient than the other or any reason why i would choose one over the other in a particular scenario ?

Thank You

Answer

Justin picture Justin · May 15, 2012

Main difference to me is somewhat theoretical. If you had an infinite sized graph then DFS would never find an element if it exists outside of the first path it chooses. It would essentially keep going down the first path and would never find the element. The BFS would eventually find the element.

If the size of the graph is finite, DFS would likely find a outlier (larger distance between root and goal) element faster where BFS would find a closer element faster. Except in the case where DFS chooses the path of the shallow element.

Related questions

Explanation of Algorithm for finding articulation points or cut vertices of a graph

I have searched the net and could not find any explanation of a DFS algorithm for finding all articulation vertices of a graph. There is not even a wiki page. From reading around, I got to know the basic facts …

Read More
How to find if a graph is bipartite?

I have been trying to understand the bipartite graph. To my understanding it is a graph G which can be divided into two subgraphs U and V.So that intersection of U and V is a null set and union …

Read More
Algorithm for diameter of graph?

If you have a graph, and need to find the diameter of it (which is the maximum distance between two nodes), how can you do it in O(log v * (v + e)) complexity. Wikipedia says you can do this using …

Read More