Module 3: Graph Algorithms & Network Analysis

Primary text: The Algorithm Design Manual (Skiena) for problem-driven framing
Selective support: Introduction to Algorithms (CLRS) for proofs and depth, Algorithms (Sedgewick) for visual intuition and implementation, Competitive Programming for applied variants, Grokking Algorithms for entry-level reminders

This guide is the primary teacher. You do not need to read the source books front-to-back to complete this module. You do need to become operationally strong at choosing a graph model, picking the right traversal or shortest-path algorithm, and defending each choice with a running-time and correctness argument.

Scope of This Module

This module is not a tour of clever graph tricks. It is where you learn to turn informal "nodes and edges" talk into a precise graph problem, choose an algorithm whose preconditions actually match, and argue for correctness.

What it covers in depth:

graphs as mathematical objects (directed/undirected, weighted, simple/multi) and the problem-recognition step
adjacency-list and adjacency-matrix representations and their operational tradeoffs
BFS as a layered traversal and as the algorithm for unweighted shortest paths
DFS, discovery/finish times, and the tree/back/forward/cross edge classification
connected and strongly connected components, and DAG-based algorithms via topological sort
single-source shortest paths via Dijkstra and Bellman-Ford, all-pairs shortest paths via Floyd-Warshall
minimum spanning trees through the cut and cycle properties, realized by Kruskal and Prim
maximum flow, the Ford-Fulkerson method, max-flow min-cut duality, and bipartite matching as a flow instance

What it deliberately does not try to finish here:

planarity algorithms, graph minors, or graph coloring theory beyond recognition
advanced flow algorithms in full (Dinic, push-relabel) beyond conceptual overview
full treatments of approximation and NP-hard graph optimization; selected variants here only illustrate changed assumptions
large-scale graph systems, distributed graph processing, and graph databases

If you can code BFS and Dijkstra but cannot say which shortest-path problem variant you are solving or why, the module is not complete.

Before You Start

Complete the Prerequisite Diagnostic on queues, stacks, invariants, heaps, cost models and record identity. Dijkstra's proof and graph connectivity are taught here, not required as prior mastery.

Plan 85–120 focused hours, approximately 9–12 weeks at 10 hours per week. This is an author estimate pending learner pilots. Repair missing prerequisites before the relevant block; completion depends on evidence, not elapsed time.

What This Module Is For

Graphs are the dominant modeling abstraction in computer science. Later work repeatedly asks questions like:

which components or services depend on which, and in what order should they be built?
what is the cheapest route in a road, compute, or network graph?
which users are connected, and how densely?
where is the bottleneck in a network, and how much traffic can it carry?
which allowed worker/job pairs maximize cardinality, and which extra requirements change that model?

This module builds the graph reasoning needed for:

compilers and build systems (dependency ordering, SCCs, DAG scheduling)
routing, networking, and distributed systems (shortest paths, spanning structures, cuts)
data-heavy engineering (recommendation, social graphs, knowledge graphs)
optimization and operations research (matching, assignment, flow)
algorithm interviews and competitive programming fluency

You are learning to see the graph hiding inside an informally stated problem.

Concept Map

How To Use This Module

Work in order. Representations and traversals underlie every later algorithm; skipping them makes the weighted and flow material feel arbitrary.

Cluster 1: Graph Models and Representations

Order	Concept	Type	Focus
1	What a Graph Is	PRIMARY	Vertices, edges, directed vs undirected, weighted, simple vs multi
2	Adjacency List vs Adjacency Matrix	PRIMARY	Space/time tradeoffs that govern later algorithm choices
3	Representing Special Graphs	SUPPORTING	DAGs, trees, bipartite, and planar as modeling vocabulary
4	Graph Problem Recognition	PRIMARY	Turning real problems into a precise graph instance

Cluster mastery check: Can you state the graph (vertices, edges, directedness, weights) before naming any algorithm?

Cluster 2: Graph Traversals

Order	Concept	Type	Focus
5	BFS and Unweighted Shortest Paths	PRIMARY	Level-by-level exploration and why BFS yields hop-count shortest paths
6	DFS and the Edge Taxonomy	PRIMARY	Discovery/finish times and tree/back/forward/cross edges
7	Connected and Strongly Connected Components	PRIMARY	Kosaraju and Tarjan strategies for SCCs
8	Topological Sort and DAG Algorithms	PRIMARY	Linear orderings and DAG-based shortest and longest paths

Cluster mastery check: Can you predict the BFS and DFS trees on a small graph before running them, and explain what each edge type would look like?

Cluster 3: Shortest Paths

Order	Concept	Type	Focus
9	Shortest Path Problem Variants	PRIMARY	Single-source, all-pairs, single-pair, and negative-edge cases
10	Dijkstra's Algorithm	PRIMARY	Relaxation, priority queue, and correctness for nonnegative weights
11	Bellman-Ford and Negative Edges	PRIMARY	Edge-relaxation rounds and negative-cycle detection
12	Floyd-Warshall and DP Shortest Paths	SUPPORTING	All-pairs via dynamic programming with intermediate-vertex subsets

Cluster mastery check: Can you pick Dijkstra, Bellman-Ford, BFS, or Floyd-Warshall given a graph's edge weights and the question being asked?

Cluster 4: Minimum Spanning Trees and Greedy on Graphs

Order	Concept	Type	Focus
13	MST, Cut Property, Cycle Property	PRIMARY	The two structural theorems that justify every MST algorithm
14	Kruskal with Union-Find	PRIMARY	Edge-sorted greedy plus disjoint-set bookkeeping
15	Prim with Priority Queue	PRIMARY	Growing one tree from a root, mirror of Dijkstra's shape
16	MST Variants and Applications	SUPPORTING	Minimax paths, tied second-best definitions, metric approximation assumptions

Cluster mastery check: Can you justify Kruskal or Prim using the cut property on a worked example rather than quoting the algorithm?

Cluster 5: Network Flow and Matching

Order	Concept	Type	Focus
17	Max Flow and Ford-Fulkerson	PRIMARY	Flow definition, residual graphs, and augmenting paths
18	Edmonds-Karp and Flow Variants	SUPPORTING	BFS levels, critical-edge analysis, and separately proved depth extensions
19	Max-Flow Min-Cut Duality	PRIMARY	The cut side of flow and where it models real problems
20	Bipartite Matching via Max Flow	SUPPORTING	Integral reduction, endpoint constraints, maximal versus maximum, and extension limits

Cluster mastery check: Can you model unit worker/job assignment as integral flow, prove both directions, and certify optimality with a matching cut bound?

Then work these practice pages:

Order	Practice path	Focus
1	Graph Representation and Traversal Lab	Representations, BFS, DFS, SCCs, topological sort
2	Shortest Paths and MST Workshop	Dijkstra, Bellman-Ford, Floyd-Warshall, Kruskal, Prim
3	Network Flow and Matching Clinic	Ford-Fulkerson, min cuts, bipartite matching
4	Implementation and Transfer Studio	Eight core implementations, certificate checks and explicit depth extensions

Use Module Quiz after the concept and practice path. Use Reference and Selective Reading and Learning Resources only for targeted reinforcement.

Learning Objectives

By the end of this module you should be able to:

Model a real problem as a graph, stating vertices, edges, directedness, weights, and special structure explicitly.
Choose adjacency list vs matrix with an argument about |V|, |E|, and the operations you need.
Implement BFS and DFS, report their time and space bounds, and classify DFS edges on a directed graph.
Compute connected components and strongly connected components, and produce a topological order on a DAG.
Pick between BFS, Dijkstra, Bellman-Ford, and Floyd-Warshall based on edge weights and question type.
State and apply the cut and cycle properties, implement Kruskal, and derive Prim with an optional heap-based implementation.
Define flow networks, execute Ford-Fulkerson, explain the max-flow min-cut theorem, and model bipartite matching as flow.
Defend any algorithmic choice with a running-time analysis and a correctness sketch, not by pattern recognition alone.

Outputs

Eight core implementations in five runnable labs, with edge-aware path, partition, forest, flow/cut and matching evidence.
Twenty practice tasks with preserved attempts and feedback from separate solutions.
A model/certificate record explaining assumptions, correctness, costs, counterexamples, assistance and repaired failures.
A dependency-planner capstone separating cycles, blocked tasks and resource-qualified schedule claims.
An eight-competency independent assessment, remediation and a delayed unseen transfer task. Prim, matrix DP, Tarjan and stronger flow methods are explicit depth extensions rather than unexplained additional deliverables.

Completion Standard

Use Competencies, Evidence, and Remediation: at least level 2 in every competency, passing lab contracts, source/proof review and a completed evidence record. Accept different valid tied witnesses. Do not replace a missing proof with more code, a first-try speed requirement or an arbitrary mistake quota.

Certificates and Engineering Contracts explains why numeric answers alone are insufficient and how to verify output independently.

Reading Policy

Concept pages are the main path.
Local book chunks are selective reinforcement, not a second syllabus.
Read only if stuck means try the concept page, self-check, and drill first.
Optional deep dive means additional nuance or exercise volume, not required progression.
The five core labs are required; optional depth implementations are identified separately in the studio.

Suggested Study Sequence

Block	Work	Focused hours
Entry and lessons	Diagnostic, 20 concepts, certificate lesson and targeted reading	30–40
Guided implementations	Five labs with proof and repair	21–30
Independent practice	P1–P20 and solution review	18–26
Assessment	Independent attempt, remediation and delayed transfer	8–12
Integration	Dependency planner and changed requirement	8–12

Total: 85–120 hours. Optional extensions add work beyond this estimate. Pause to repair failed invariants or contracts before moving to more complex algorithms.

Reference

For book indexes, topic assignments and local source locations, use Reference and Selective Reading.

Rich Learning Pages

Scope of This Module​

Before You Start​

What This Module Is For​

Concept Map​

How To Use This Module​

Cluster 1: Graph Models and Representations​

Cluster 2: Graph Traversals​

Cluster 3: Shortest Paths​

Cluster 4: Minimum Spanning Trees and Greedy on Graphs​

Cluster 5: Network Flow and Matching​

Learning Objectives​

Outputs​

Completion Standard​

Reading Policy​

Suggested Study Sequence​

Reference​

Rich Learning Pages​

Assessment and Review Navigation​