Project 9: Graph Traversal Visualizer

A self-contained deep-dive from the canonical Math from Foundations to Machine Learning curriculum.

  • Difficulty: Intermediate
  • Time: 8-14 hours (about a weekend)
  • Language: Python (alternatives: JavaScript, C++)
  • Prerequisites: Projects 2 and 8
  • Source: Prog P06

What You Will Build

Build an interactive or frame-by-frame visualizer for breadth-first search (BFS) and depth-first search (DFS) on user-defined directed or undirected graphs. Support adjacency-list input, validate missing/duplicate nodes, and display the active node, frontier data structure, visited set, traversal tree, and discovery order after every operation. BFS should reconstruct shortest unweighted paths; DFS should reveal branches, backtracking, and connected/reachable components. Deterministic neighbor ordering and a seeded graph generator make runs testable and comparable.

Real World Outcome

Selecting a start and goal animates BFS expanding in layers and returns a highlighted shortest path with distance. Switching to DFS shows a different exploration tree and explicit backtracking. Disconnected nodes remain visibly unvisited, and directed edges are respected. A textual trace makes the algorithm understandable even without the animation and can be compared against expected queue/stack states.

Core Question

How does the choice of frontier discipline—first-in-first-out versus last-in-first-out—change exploration order and the guarantees you get?

Concepts You Must Understand First

  1. Graph vocabulary: vertices, edges, direction, paths, cycles, components, and reachability.
  2. Adjacency representations: lists suit sparse graphs; matrices make edge lookup direct but consume more space.
  3. Queue and stack behavior: BFS uses FIFO; iterative DFS uses LIFO, while recursive DFS uses the call stack.
  4. Visited invariants: mark discovery early enough to avoid repeated insertion and cycle loops.
  5. Shortest unweighted paths: BFS layer number equals edge distance. See Cormen et al., Introduction to Algorithms, graph traversal chapters.

Build Milestones

  1. Parse directed/undirected graphs and render nodes, edges, labels, and disconnected components.
  2. Implement BFS as an event generator emitting enqueue, dequeue, discover, and finish events.
  3. Implement iterative or recursive DFS with discover, edge, backtrack, and finish events.
  4. Add parent maps, traversal trees, reachability, and BFS shortest-path reconstruction.
  5. Build controls for play/pause/step/reset and tests for exact deterministic traces.

Hints in Layers

  1. Keep algorithms UI-independent by yielding immutable events; the renderer only consumes them.
  2. Sort neighbors before traversal so insertion order does not silently change teaching output.
  3. For a shortest path, follow parent[goal] backward to the start and reverse the result.

Common Pitfalls and Debugging

  • Symptom: cyclic graphs enqueue the same node many times. Cause: nodes are marked visited only when removed. Fix: mark them when discovered/enqueued.
  • Symptom: BFS returns a non-shortest path. Cause: a stack or weighted interpretation slipped in. Fix: inspect frontier events and assert nondecreasing discovery distance.
  • Symptom: animation state differs from algorithm state. Cause: mutable containers were passed to old frames. Fix: snapshot event payloads.

Definition of Done

  • Directed and undirected graph inputs are validated and rendered.
  • BFS and DFS produce deterministic, inspectable event traces.
  • The frontier, visited set, and traversal tree are visible at each step.
  • BFS reconstructs correct shortest paths in unweighted graphs.
  • Cycles, self-loops, disconnected graphs, and unreachable goals are tested.

Previous: Project 8 · Complete learning path · Next: Project 10