4.3.1.1 - Breadth-first and depth-first graph traversal (Python)
Learn how queues and stacks control the order in which a graph is explored, how to trace the changing state, and why the two traversals suit different problems.
Breadth-first search and queues
Breadth-first search explores all reachable vertices one edge away from the start before vertices two edges away, then three, and so on.
Breadth-first search
A graph traversal that explores vertices in increasing distance from a start vertex, measured in number of edges, using a first-in, first-out queue.
A traversal visits the graph systematically; a search can stop when a target is found. Keep a discovered set as well as the queue. Mark a vertex discovered when it enters the queue, so two different neighbours cannot queue it twice. Remove the front vertex, process it, then append each undiscovered neighbour to the back. The neighbour order must be stated: different legitimate orders can produce different traces within the same distance layer.
Consider this undirected graph, with each adjacency list in alphabetical order:
| Vertex | Neighbours |
|---|---|
| A | B, C |
| B | A, D, E |
| C | A, E |
| D | B |
| E | B, C, F |
| F | E |
[DIAGRAM: asset_slug: py_traversal_graph; description: Exact undirected graph with edges AB, AC, BD, BE, CE and EF.]
Start at A. In the trace, the queue's front is at the left, and the displayed queue is the state after processing the vertex.
| Processed | Queue | Newly discovered |
|---|---|---|
| — | A | A |
| A | B, C | B, C |
| B | C, D, E | D, E |
| C | D, E | none; E is already discovered |
| D | E | none |
| E | F | F |
| F | empty | none |
Thus the processing order is A, B, C, D, E, F. To find an unweighted shortest path, store a predecessor when a vertex is first discovered. Here E is discovered from B and F from E, giving A → B → E → F, three edges. A BFS first reaches F with the fewest edges because it completes earlier layers first. If edges represent unequal costs, fewest edges need not mean lowest cost.
Observe breadth-first layers
{"code":"from collections import deque\n\ngraph = {'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'E'], 'D': ['B'], 'E': ['B', 'C', 'F'], 'F': ['E']}\nqueue = deque(['A'])\ndiscovered = {'A'}\nwhile queue:\n vertex = queue.popleft()\n print(vertex, end=' ')\n for neighbour in graph[vertex]:\n if neighbour not in discovered:\n discovered.add(neighbour)\n queue.append(neighbour)\nprint()","instructions":"Predict the processing order before Run. Then reverse every neighbour list by adding graph = {v: list(reversed(ns)) for v, ns in graph.items()} before queue is created. Predict and run again: which order changes, and why do the distance layers remain?","files":[],"original_filename":"main.py","runtime_profile":"python-console-v1","file_mode":"fresh"}
Depth-first search and stacks
Depth-first search follows one branch as far as it can before returning to an earlier branching point.
A stack provides last-in, first-out storage. Recursive DFS uses the call stack: visit the vertex, then recursively visit each still-unvisited neighbour; when a call has no new neighbour, it returns. For the same graph and alphabetical neighbour order, recursive DFS processes A, B, D, E, C, F. After D returns to B, exploration continues through E. At E, C is visited before F, even though C is nearer the original start.
def dfs(graph, vertex, visited, order):
visited.add(vertex)
order.append(vertex)
for neighbour in graph[vertex]:
if neighbour not in visited:
dfs(graph, neighbour, visited, order)
The visit test prevents the undirected edge back to the parent, and the B–E–C–A cycle, from causing endless recursion. An explicit stack is another implementation. If it marks on popping, it must skip vertices already processed; if it marks on pushing, some orders differ from recursive DFS. Never infer a precise trace from the word “DFS” alone: use the supplied algorithm and push/visit rules. For a stack, state which end is the top and the order in which neighbours are pushed.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account