When is it practical to use Depth-First Search (DF

问题:

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?

回答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.

回答2:

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.

回答3:

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.

回答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.

回答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.

回答6:

One important advantage of BFS would be that it can be used to find the shortest path between any two nodes in an unweighted graph. Whereas, we cannot use DFS for the same.

回答7:

When you approach this question as a programmer, one factor stands out: if you're using recursion, then depth-first search is simpler to implement, because you don't need to maintain an additional data structure containing the nodes yet to explore.

Here's depth-first search for a non-oriented graph if you're storing “already visited” information in the nodes:

def dfs(origin):                               # DFS from origin:
    origin.visited = True                      # Mark the origin as visited
    for neighbor in origin.neighbors:          # Loop over the neighbors
        if not neighbor.visited: dfs(next)     # Visit each neighbor if not already visited

If storing “already visited” information in a separate data structure:

def dfs(node, visited):                        # DFS from origin, with already-visited set:
    visited.add(node)                          # Mark the origin as visited
    for neighbor in node.neighbors:            # Loop over the neighbors
        if not neighbor in visited:            # If the neighbor hasn't been visited yet,
            dfs(node, visited)                 # then visit the neighbor
dfs(origin, set())

Contrast this with breadth-first search where you need to maintain a separate data structure for the list of nodes yet to visit, no matter what.

回答8:

For BFS, we can consider Facebook example. We receive suggestion to add friends from the FB profile from other other friends profile. Suppose A->B, while B->E and B->F, so A will get suggestion for E And F. They must be using BFS to read till second level. DFS is more based on scenarios where we want to forecast something based on data we have from source to destination. As mentioned already about chess or sudoku. Once thing I have different here is, I believe DFS should be used for shortest path because DFS will cover the whole path first then we can decide the best. But as BFS will use greedy's approach so might be it looks like its the shortest path, but the final result might differ. Let me know whether my understanding is wrong.

回答9:

Some algorithms depend on particular properties of DFS (or BFS) to work. For example the Hopcroft and Tarjan algorithm for finding 2-connected components takes advantage of the fact that each already visited node encountered by DFS is on the path from root to the currently explored node.

回答10:

According to the properties of DFS and BFS. For example,when we want to find the shortest path. we usually use bfs,it can guarantee the 'shortest'. but dfs only can guarantee that we can come from this point can achieve that point ,can not guarantee the 'shortest'.

回答11:

Because Depth-First Searches use a stack as the nodes are processed, backtracking is provided with DFS. Because Breadth-First Searches use a queue, not a stack, to keep track of what nodes are processed, backtracking is not provided with BFS.

回答12:

When tree width is very large and depth is low use DFS as recursion stack will not overflow.Use BFS when width is low and depth is very large to traverse the tree.

回答13:

This is a good example to demonstrate that BFS is better than DFS in certain case. https://leetcode.com/problems/01-matrix/

When correctly implemented, both solutions should visit cells that have farther distance than the current cell +1. But DFS is inefficient and repeatedly visited the same cell resulting O(n*n) complexity.

For example,

1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
0,0,0,0,0,0,0,0,

回答14:

It depends on the situation it is used in. Whenever we have a problem of traversing a graph, we do it for some purpose. When there is a problem of finding shortest path in an unweighted graph, or finding if a graph is bipartite, we can use BFS. For problems of cycle detection or any logic requiring backtracking, we can use DFS.

回答15:

This question is somewhat old, but a great example is from the modern video game "Bit Heroes". In a typical boss dungeon, your goal is to defeat the boss, after which you have the option to either quit that particular dungeon or continue exploring it for loot. But in general, the bosses are far from your spawn point. The game offers an automatic dungeon-traversal feature that basically takes your character through the dungeon, encountering enemies as it goes. This is implemented with a Depth-First Search algorithm, as the goal is to go as deep into the dungeon as possible before backtracking.