A route network can branch, reconnect and contain loops. A tree gives each non-root node one parent, but many networks need a more general model. A graph represents those connections; a traversal supplies a rule for exploring them without repeatedly revisiting the same vertices.
Reading route¶
Graph concepts and modelling: distinguish vertices, edges, direction, weights, paths and cycles.
Representing graphs: connect adjacency lists and matrices to the operations they support.
Graph operations: build, query and update a simple graph while preserving its representation contract.
Breadth-first search: maintain a queue, discover each vertex once and recover shortest hop paths.
Depth-first search: follow an active path, return from calls and distinguish discovery from completion.
Reachability and components: restart traversal to cover an undirected graph, including isolated vertices.
Traversal costs and choices: count examined entries, state assumptions and choose a traversal for the question.
Read queues and stacks, recursive calls and algorithm analysis first. Priority queues are not needed for this topic. Next, Topic 12: union–find maintains connectivity as connections arrive. Topic 13 will add dependency ordering and weighted routes.
The shared lecture graph has vertices A through H and eight undirected edges. All code assumes well-formed adjacency lists, hashable non-None vertex labels (strings in the shared trace), and the stored neighbour order. The graph remains unchanged during traversal. No notebook is needed.
Contracts, implementations and checks¶
Read the graph model and representation before tracing discovery, expansion and completion. Use the same stored neighbour order as the diagram when predicting exact parents or visit order; tied valid answers can differ under another order.
Graph mutation is separate from algorithms that observe a fixed graph and return snapshots. The operation contract states returns and errors; the traversal comparison distinguishes reachable-region results, full partitions, working state and output storage. Directed cycle/SCC algorithms remain extensions.
Code listings offer Python, JavaScript and Julia tabs where a runnable example is present. Python remains the explanation and trace language; see the language guide for native conventions and runnable topic downloads.