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

Question

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

Solution 1

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.

Solution 2

In general, BFS is better for problems related to finding the shortest paths or somewhat related problems. Because here you go from one node to all node that are adjacent to it and hence you effectively move from path length one to path length two and so on.

While DFS on the other end helps more in connectivity problems and also in finding cycles in graph(though I think you might be able to find cycles with a bit of modification of BFS too). Determining connectivity with DFS is trivial, if you call the explore procedure twice from the DFS procedure, then the graph is disconnected (this is for an undirected graph). You can see the strongly connected component algorithm for a directed graph here, which is a modification of DFS. Another application of the DFS is topological sorting.

These are some applications of both the algorithms:

DFS:

Connectivity
Strongly Connected Components
Topological Sorting

BFS:

Shortest Path(Dijkstra is some what of a modification of BFS).
Testing whether the graph is Bipartitie.

Comments

[jedd.ahyoung]

This is not a bad answer, but DFS and BFS can both fail in the infinite case - DFS can fail if a graph is infinitely deep, while BFS can work. However, DFS will work if the graph is not infinitely deep, but infinitely broad - while BFS will fail. Traversing infinite graphs (from what I understand) is much different than traversing finite graphs.