Skip to main content

Module 3: Graph Algorithms & Network Analysis: Guided Labs

These labs turn graph reading into evidence. Commit outputs to your algorithms repo or learning notebook.

Lab 1: Graph Model Trace​

Goal: turn an informal problem into a precise graph before choosing an algorithm.

Choose three scenarios:

  • course prerequisites
  • subway routes
  • package dependency installation

For each, write:

FieldAnswer
Vertices
Edges
Directed?
Weighted?
Special structureDAG, tree, bipartite, dense, sparse, unknown
Likely algorithm
Why this algorithm fits

Evidence: one table per scenario plus one paragraph comparing the three models.

Lab 2: BFS and DFS Side-by-Side​

Goal: see how traversal choice changes the evidence you get.

Use the same graph for both traversals. Record:

  • BFS queue state after each step
  • BFS distance labels
  • DFS discovery/finish times
  • DFS tree/back/forward/cross edges

Evidence: one hand trace and one implementation test that confirms the trace.

Lab 3: Shortest-Path Algorithm Clinic​

Goal: choose by preconditions.

Create four graphs:

  1. unweighted graph
  2. weighted graph with nonnegative edges
  3. weighted graph with one negative edge and no negative cycle
  4. weighted graph with a negative cycle

For each graph, answer:

  • BFS, Dijkstra, Bellman-Ford, or Floyd-Warshall?
  • What precondition decides it?
  • What output should the algorithm produce?

Evidence: one algorithm-choice table and at least two hand traces.

Lab 4: MST vs Shortest Path​

Goal: stop confusing two different questions.

Build a 6-vertex weighted undirected graph. Then compute:

  • shortest path from A to F
  • minimum spanning tree

Write one paragraph explaining why the MST is not a route planner and why shortest path is not a network-design solution.

Evidence: graph drawing, MST edge set, shortest path, and explanation.

Lab 5: Flow Modeling​

Goal: expose the flow network hiding inside an assignment problem.

Model tasks assigned to workers:

  • source connects to each worker with capacity 1
  • each worker connects to tasks they can do with capacity 1
  • each task connects to sink with capacity 1

Run max-flow by hand on a small instance with 3 workers and 4 tasks.

Evidence: flow graph, residual graph after each augmentation, final matching.