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
approximation algorithms for NP-hard graph problems (that is Semester 4 territory)
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

Answer these closed-book before starting the main path:

What is the difference between a path, a walk, and a cycle in a graph?
Why do we distinguish directed from undirected edges when talking about reachability?
When you implement BFS from Semester 0 instincts, what data structure holds the frontier and why?
Why does Dijkstra fail on graphs with negative edge weights?
What is the abstract role of a priority queue in the algorithms you already know?

Diagnostic Interpretation

4-5 solid answers

You are ready for the full path.

2-3 solid answers

Continue, but expect extra time in the traversal and shortest-path clusters.

0-1 solid answers

Revisit Module 2 priority queues and Semester 0 queue/stack material first. Graph algorithms reuse those structures heavily.

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 pairs should be matched (tasks to workers, ads to slots, residents to hospitals)?

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	Bottleneck MST, Steiner approximation, network design

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, Capacity Scaling, Push-Relabel	SUPPORTING	Concrete polynomial-time realizations of the method
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	Reduction to flow and Hopcroft-Karp intuition

Cluster mastery check: Can you take a non-flow-looking problem (task assignment, pixel labeling, project selection) and expose the flow graph hiding inside it?

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	Code Katas	Implementation drills for every named algorithm

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, and implement Kruskal (with union-find) and Prim (with a heap).
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

a graph-algorithms repository with tested implementations of BFS, DFS, Kosaraju SCC, topological sort, Dijkstra (heap), Bellman-Ford, Floyd-Warshall, Kruskal (union-find), Prim (heap), and Ford-Fulkerson
one modeling notebook translating at least 8 informally stated problems into explicit graph instances
one algorithm-selection sheet covering at least 10 shortest-path scenarios with justified choices
one MST sheet with at least 3 cut-property arguments written in sentence form
one flow sheet modeling at least 3 non-flow-looking problems (matching, project selection, image segmentation) as max-flow instances
one mistake log naming at least 10 reasoning errors such as ran Dijkstra on negative edges, used matrix on a sparse graph, confused SCC with CC, forgot to reverse the graph in Kosaraju, or missed a residual edge
one short memo explaining how the module's tools carry into systems work (dependency graphs, build orders, routing)

Completion Standard

You have completed Module 3 when all of these are true:

you state the graph model before you name an algorithm
you justify adjacency-list vs matrix by complexity, not by habit
you can trace BFS and DFS on paper and explain the resulting trees and edge classes
you can run Dijkstra and Bellman-Ford by hand on a 6-8 vertex graph and defend the relax order
you can execute Kruskal and Prim by hand and cite the cut property during the argument
you can take a real problem (assignment, scheduling, bottleneck) and turn it into a flow or matching instance
you can read a new graph problem and decide "this is a DAG topo question" or "this is really min-cut" within seconds

If the algorithm runs but you cannot explain why the answer is correct or why this algorithm fits, the module is not complete.

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.
Because graph algorithms reward implementation experience, the Code Katas are required, not optional.

Suggested Weekly Flow

Day	Work
1	Concepts 1-4 and a modeling sheet translating 3 informal problems into graphs
2	Concepts 5-6, implement BFS and DFS from scratch, and run both on one worked graph
3	Concepts 7-8, implement Kosaraju and topological sort
4	Concepts 9-10, implement Dijkstra with a binary heap, hand-trace one example
5	Concepts 11-12, implement Bellman-Ford and Floyd-Warshall
6	Concepts 13-15, implement Kruskal (union-find) and Prim (heap), write a cut-property argument
7	Concepts 16-20, Ford-Fulkerson implementation, practice pages, and quiz

Reference

If you need exact links into the local chunked books, use Reference and Selective Reading.

Rich Learning Pages

Scope of This Module​

Before You Start​

Diagnostic Interpretation​

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 Weekly Flow​

Reference​

Rich Learning Pages​