When should you use BFS rather than DFS in a graph problem?
You use BFS when the question is about distance, and you use DFS when the question is about reachability or about the shape of the tree.
from collections import deque
def bfs_distances(graph, start):
distance = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbour in graph[node]:
if neighbour not in distance:
distance[neighbour] = distance[node] + 1
queue.append(neighbour)
return distance
So when should you use BFS rather than DFS? Here are the cases.
the question use
------------------------------------ ---------
the shortest path with no weights BFS
how many steps away is each node? BFS
is there any path at all? either one
count or list all the paths DFS
detect a cycle either one
a puzzle with many states BFS
And the reason is that BFS explores in order of distance. It looks at all the nodes one step away, then all the nodes two steps away, and so on. So the first time it reaches a node it has found the shortest way to it.
And DFS goes as deep as it can first and then comes back. So it can find a node in a long number of steps even when a short way exists, and that is why you cannot use DFS for shortest paths.
And there is one more thing that BFS is good at. When every edge has the same cost, BFS is the shortest path algorithm. And when the edges have different costs then BFS does not work and you need something like Dijkstra's algorithm instead.
And the space cost is worth knowing about too. BFS holds a whole level of the graph in the queue at once, so it uses more memory on a wide graph. DFS only holds the path that it is on, so it uses less memory on a wide graph but it can go very deep on a long one.
So the rule to remember is this. BFS for distance, DFS for structure.
The next two questions in this topic show the DFS code and the shortest path.