Breadth-first search (BFS) traverses a graph outward from a known source, visiting vertices in nondecreasing order of their distance in edges. It fits problems such as finding the fewest-block delivery route or reaching a goal from a specified starting point. section 14.0 section 14.3.5
Implement BFS with a queue, discovery distances, and parent links:
- Initialize the source with distance 0, enqueue it, and mark every other vertex as undiscovered. section 14.3.2
- Dequeue the next vertex and optionally stop when it satisfies the goal condition. section 14.3.2
- Scan its adjacency list; for each undiscovered neighbor, assign the current distance plus one, record its parent, and enqueue it. section 14.3.2
- Continue until the queue is empty, or reconstruct a route by following parent links from the destination. section 14.3.2 section 14.3.6
Fewest-block delivery route
Represent intersections and streets as a graph, start BFS at the warehouse, and stop when the customer’s vertex is dequeued. The resulting parent links describe a shortest path by number of edges. Removing one street can change the route completely, so the modified graph provides a useful exercise. section 14.3.6
Listing 14.2 The bfs method
function bfs(graph, start, isGoal) #1
queue ← new Queue() #2
queue.insert(start) #3
distances ← new HashTable() #4
parents ← new HashTable() #5
for v in graph.vertices do #6
distances[v] ← inf
parents[v] ← null
distances[start] ← 0 #7
while not queue.empty() do #8
v ← queue.dequeue() #9
if isGoal(v) then #10
return (v, parents)
for e in graph.adjacencyList[v] do #11
u ← e.dest
if distances[u] == inf then #12
distances[u] ← distances[v] + 1 #13
parents[u] ← v
queue.enqueue(u)
return (null, parents) #14
Use the complete pseudocode to inspect queue operations, distance initialization, discovery checks, parent assignment, and goal handling. section 14.3.2
