Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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

like image 266
Kris Avatar asked May 15 '12 17:05

Kris


People also ask

Which is better DFS or BFS?

DFS is more space-efficient than BFS, but may go to unnecessary depths. Their names are revealing: if there's a big breadth (i.e. big branching factor), but very limited depth (e.g. limited number of "moves"), then DFS can be more preferrable to BFS.

How is best first search better than BFS and DFS?

ABSTRACT. Best-first search (BFS) expands the fewest nodes among all admissible algorithms using the same cost function, but typically requires exponential space. Depth-first search needs space only linear in the maximum search depth, but expands more nodes than BFS.

What is the advantage of depth first search Mcq?

Explanation: The Depth First Search will make a graph which don't have back edges (a tree) which is known as Depth First Tree. 5. A person wants to visit some places. He starts from a vertex and then wants to visit every vertex till it finishes from one vertex, backtracks and then explore other vertex from same vertex.


2 Answers

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.

like image 136
Justin Avatar answered Oct 24 '22 15:10

Justin


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.

like image 27
sukunrt Avatar answered Oct 24 '22 16:10

sukunrt