Why are you guaranteed to find your result if it is in the graph with BFS but not with DFS?

Question

I've read somewhere that DFS is not gaurenteed to find a solution while BFS is.. why? I don't really get how this is true.. could someone demonstrate a case for me that proves this?

Answer 1

DFS, since its a Depth first search, could get stuck in an infinite branch and never reach the vertex you're looking for. BFS goes through all vertices at the same distance from the root each iteration, no matter what branch they're on so it will find the desired vertex eventually.
example:

root -> v1 -> v2 -> v3 -> ... goes on forever
|-> u.

in this example, if DFS begins at the root and then goes on to v1. it will never reach u since the branch it entered is infinite. BFS will go from root to either v1 or u and then to the other.

Answer 2

The output of both DFS and BFS (on graphs with a finite number of vertices) terminate and yield a path (or rather a tree, but the OP only seems to be interested in one path of that tree). It does not matter whether there are cycles in the graph, because both procedures keep a record of which vertices have already been visited and thus avoids visiting the same vertex more than once. Any sane implementation of DFS/BFS does this - otherwise you'd be constrained to acyclic graphs only (see the pseudocode given in CLRS).

As @yurib mentioned, if the graph has an infinite number of nodes, dfs can take forever. Since there are infinite nodes, we cannot practically keep track of which vertices were already visited (that would take potentially infinite memory) and even if we did, there maybe be an infinite path containing unique vertices which does not contain the vertex we are looking for.

However, that is not the only reason DFS does not always find the shortest path. Even in finite graphs, DFS may fail to find the shortest path.

The main reason is that BFS always explores all nodes at distance x from the root before moving on to those at distance x+1. Thus if a node is found at distance k, we can be sure the minimum distance from the root to that node is k and not k-1, k-2,...,0 (otherwise we would have encountered it earlier).

DFS, on the other hand, basically explores nodes along one path until there are no more new nodes down that path before looking at a different path. DFS just explores each successor of a node one by one, in an essentially arbitrary order. This means it may find a longer path to the target node just because it just happened to explore that path first.

In the image above, a BFS would explore B and E first, and then reach D via E - giving us the path to D as root->E->D. A DFS might start search from B first, thus finding the path root->B->C->D, which is clearly not the shortest.

Notice the crucial decision was to go for exploring B before E. A DFS might well have chosen E and arrived at the correct answer. But there is in general no way to know which path to go down first (if we knew that we would know the shortest path anyway). For a DFS the path which it finds simply depends on the order in which it explores the successor nodes, which may or may not yield a shortest path.

Answer 3

@yurib is correct, but there is a further complication.

If the desired vertex is NOT in the graph, then neither BFS or DFS will terminate if there is a cycle ... unless you take steps to detect cycles. And if you are taking steps to detect cycles, both BFS and DFS will terminate.