When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)?

Question

I understand the differences between DFS and BFS, but I'm interested to know when it's more practical to use one over the other?

Could anyone give any examples of how DFS would trump BFS and vice versa?

Solution 1

That heavily depends on the structure of the search tree and the number and location of solutions (aka searched-for items).

• If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better.

• If the tree is very deep and solutions are rare, depth first search (DFS) might take an extremely long time, but BFS could be faster.

• If the tree is very wide, a BFS might need too much memory, so it might be completely impractical.

• If solutions are frequent but located deep in the tree, BFS could be impractical.

• If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).

But these are just rules of thumb; you'll probably need to experiment.

I think in practice you'll usually not use these algorithms in their pure form anyway. There could be heuristics that help to explore promising parts of the search space first, or you might want to modify your search algorithm to be able to parallelize it efficiently.

Solution 2

Depth-first Search

Depth-first searches are often used in simulations of games (and game-like situations in the real world). In a typical game you can choose one of several possible actions. Each choice leads to further choices, each of which leads to further choices, and so on into an ever-expanding tree-shaped graph of possibilities.

For example in games like Chess, tic-tac-toe when you are deciding what move to make, you can mentally imagine a move, then your opponent’s possible responses, then your responses, and so on. You can decide what to do by seeing which move leads to the best outcome.

Only some paths in a game tree lead to your win. Some lead to a win by your opponent, when you reach such an ending, you must back up, or backtrack, to a previous node and try a different path. In this way you explore the tree until you find a path with a successful conclusion. Then you make the first move along this path.

---

Breadth-first search

The breadth-first search has an interesting property: It first finds all the vertices that are one edge away from the starting point, then all the vertices that are two edges away, and so on. This is useful if you’re trying to find the shortest path from the starting vertex to a given vertex. You start a BFS, and when you find the specified vertex, you know the path you’ve traced so far is the shortest path to the node. If there were a shorter path, the BFS would have found it already.

Breadth-first search can be used for finding the neighbour nodes in peer to peer networks like BitTorrent, GPS systems to find nearby locations, social networking sites to find people in the specified distance and things like that.

Solution 3

Nice Explanation from http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/

An example of BFS

Here’s an example of what a BFS would look like. This is something like Level Order Tree Traversal where we will use QUEUE with ITERATIVE approach (Mostly RECURSION will end up with DFS). The numbers represent the order in which the nodes are accessed in a BFS:

In a depth first search, you start at the root, and follow one of the branches of the tree as far as possible until either the node you are looking for is found or you hit a leaf node ( a node with no children). If you hit a leaf node, then you continue the search at the nearest ancestor with unexplored children.

An example of DFS

Here’s an example of what a DFS would look like. I think post order traversal in binary tree will start work from the Leaf level first. The numbers represent the order in which the nodes are accessed in a DFS:

Differences between DFS and BFS

Comparing BFS and DFS, the big advantage of DFS is that it has much lower memory requirements than BFS, because it’s not necessary to store all of the child pointers at each level. Depending on the data and what you are looking for, either DFS or BFS could be advantageous.

For example, given a family tree if one were looking for someone on the tree who’s still alive, then it would be safe to assume that person would be on the bottom of the tree. This means that a BFS would take a very long time to reach that last level. A DFS, however, would find the goal faster. But, if one were looking for a family member who died a very long time ago, then that person would be closer to the top of the tree. Then, a BFS would usually be faster than a DFS. So, the advantages of either vary depending on the data and what you’re looking for.

One more example is Facebook; Suggestion on Friends of Friends. We need immediate friends for suggestion where we can use BFS. May be finding the shortest path or detecting the cycle (using recursion) we can use DFS.

Solution 4

Breadth First Search is generally the best approach when the depth of the tree can vary, and you only need to search part of the tree for a solution. For example, finding the shortest path from a starting value to a final value is a good place to use BFS.

Depth First Search is commonly used when you need to search the entire tree. It's easier to implement (using recursion) than BFS, and requires less state: While BFS requires you store the entire 'frontier', DFS only requires you store the list of parent nodes of the current element.

Solution 5

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.

---

On IDDFS

It should be mentioned that there's a less-known variant that combines the space efficiency of DFS, but (cummulatively) the level-order visitation of BFS, is the iterative deepening depth-first search. This algorithm revisits some nodes, but it only contributes a constant factor of asymptotic difference.

View more solutions

Comments

[Hans-Peter Störr]

Maybe you could mention the full terms for DFS and BFS to the question - people might not know these abbreviations.

[Gilles 'SO- stop being evil']

Similar question on Computer Science: graph searching: Breadth-first vs. depth-first

[Ciro Santilli OurBigBook.com]

possible duplicate of Graphs data structure: DFS vs BFS?

[Kanagavelu Sugumar]

programmerinterview.com/index.php/data-structures/dfs-vs-bfs

[Yossarian42]

note mentions some application scenarios of BFS and DFS

[R B]

It's not necessarily more space efficient.. consider a path graph for example.

[Kyle Delaney]

What is "post order traversal in binary tree"?

[Naveen Gabriel]

Does DFS find shortest path better than BFS? I think it is other way around. I think BFS find shortest path. Isn't it?

[learntogrow-growtolearn]

Would have appreciated more if you would have given the credits to the source. The comparison part is picked up from "Data Structures made easy in Java" by Narasimha Karumanchi.

[Kanagavelu Sugumar]

Sure i can update that, but not expecting anyone appreciation here. Just want to help poor techie like me.

[Dave]

@KyleDelaney there are three orders in which you can traverse a tree -- pre-order, inorder and postorder. They correspond to prefix infix and postfix notation respectively. When you traverse the tree down and then back up, if you pick a node the first time you visit it that is pre-order, if the second time it's inorder, if the last time it's postorder. You can actually serialize the tree this way and as long as you remember the order you used you can rebuild the tree from the serialization.

[Marek Marczak]

AFAIK recursion generally needs more memory than iteration.

[Hans-Peter Störr]

@MarekMarczak I don't quite see what you want to say. If you take BFS as iteration - if the solution space isn't easily enumerable you might have to store the whole n-th level of the search tree in memory to enumerate the n+1-th level.

[Oskarzito]

Now my comment is a bit late. But to find the shortest path, BFS should be used. However, "DFS is more based on scenarios where we want to forecast something based on data we have from source to destination" is a brilliant thing you said! Kudos!!

[Clint Deygoo]

@MarekMarczak The iterative version of DFS uses a stack. Recursion vs. Iteration is a whole separate topic.

[montonero]

If you add an empty line before the list, the answer will look much better.

[MedicineMan]

the family tree example was just fantastic. Can I give two upvotes?

[ThePartyTurtle]

Just another case that came to mind: BFS is useful (necessary) in a case where a graph is "infinite". Like say, a chess board that extends to infinity in all directions. DFS will never return. BFS is guaranteed to find what it's searching for IF the condition is satisfiable.

[manesioz]

I think for the first example, the recursive call should be dfs(neighbor) and in the second example the recursive call should be dfs(neighbor, visited)

[Vishal Patwardhan]

Both look at the same implementation level. And as far as additional data structure is concerned In BFS Queue used which adds vertices yet to explore at the end whereas in DFS stack is used.both give equal running time O(#verticesvisited). To keep track of vertices visited above mentioned ways or Boolean array of vertices can be used which again doesn't distinguishes them much. BFS is layer by layer exploration whereas DFS can be said branch by branch exploration from its root till it's leaves.

[ashish_]

On a lighter note, What if the degree of nodes is also infinite in the infinite graph. In that case even if the search condition is satisfiable, but neither bfs neither dfs is gauranteed to find/return a solution !

[Ricola]

About parallelism : I don't understand how you can parallelise DFS without sharing a datastructure. How can one machine know if another machine has already visited a node? Or we don't care and let different machines visit the same nodes?

[Hans-Peter Störr]

@Ricola Parallaelism of DFS: depends on your problem. If it is a tree it's very easy - take the immediate children of the root node (or possibly at a slightly deeper level the tree doesn't spread out too much) and let every processor work on a different one of of these. If it's not a tree, you'll likely have to do some clever problem-specific thing to avoid double work.

[Ricola]

@Hans-PeterStörr if it's a tree then you can use BFS the same way. Can you give an example of a case where you can parallelize DFS but not BFS?

[Hans-Peter Störr]

@Ricola You might be right. I guess in practice you'll never use one of these algorithm in it's pure form, anyway - you'll do something clever for parallelization, employ heuristics to select paths to explore first and to truncate not promising paths, and whatnot.

[Ricola]

@Hans-PeterStörr should we edit out that part of the answer then?