Suppose you want an introduction to someone in a social network. You would ask your friends first, then friends of friends, then people another introduction away. Breadth-first search (BFS) explores a graph in that order: outward from a starting vertex, one distance at a time. section 13.13 section 1.5
A queue keeps nearer vertices ahead of farther ones. BFS processes vertices one at a time, but its queue makes the overall search expand in concentric rings. section 13.13
To find a path from a start vertex to a target:
- Put the start vertex in the queue and give it distance zero. section 13.13
- Remove the next vertex. For each destination of its outgoing edges that has not already been added, record its distance and predecessor, then add it to the queue. section 13.13
- If the target is reached, follow predecessors backward and reverse the result. If the queue empties first, no path was found. section 13.13
Why skip a vertex already in the queue? Another route to it cannot use fewer edges: the queue has already placed the nearer possibilities first. BFS therefore finds paths with the minimum number of edges from the start vertex. Depth-first search takes a different approach, following paths toward their ends. section 13.13 section 13.16
def bfs(self, start_vertex, target_vertex):
distance = {v: float('inf') for v in self._adj}
predecessor = {v: None for v in self._adj}
queue = Queue(self.vertex_count())
queue.enqueue(start_vertex) #1
distance[start_vertex] = 0
while not queue.is_empty():
u = queue.dequeue()
if u == target_vertex:
return reconstruct_path(predecessor, target_vertex)
for (_, v) in self._get_vertex(u).outgoing_edges():
if distance[v] == float('inf'):
distance[v] = distance[u] + 1
predecessor[v] = u
queue.enqueue(v)
return None #2
#1 Initially, we add the start vertex to the queue.
#2 At this point, we know there is no path from the start to the target vertex.
The Python `bfs` method uses a queue, distance values and predecessors to search for the target; it returns `None` if the queue runs out. section 13.13
def reconstruct_path(pred, target):
path = []
while target:
path.append(target)
target = pred[target]
return path[::-1] #1
#1 The list goes from target to start: we need to reverse it.
The companion function follows predecessors from the target and reverses the list to produce a path from the start. section 13.13
