Algorithms & Complexity's own Chapter 1 promised this course would build directly on its recursion and Master Theorem material. Discrete Mathematics Fundamentals' own Chapter 1 promised a graph was "technically also a kind of relation," reserved for here. Both promises land in the same place: a graph is simply things (vertices) and the connections between them (edges) — one of the most general, most reused modeling tools in all of computer science.

What a Graph Actually Is

Strip away whatever the vertices and edges represent — cities and roads, people and friendships, packages and dependencies, web pages and links — and what's left is pure structure: which things connect to which. Graph theory studies that structure directly, which is exactly why the same handful of algorithms this course covers work identically whether the vertices are cities, users, or build targets.

A Real Space Comparison: Representing a Social Network

A graph can be stored two obvious ways: an adjacency matrix (a V×V grid marking which vertex pairs connect) or an adjacency list (each vertex keeping a list of just its own neighbors). For a realistic social network — 1,000 users, each with roughly 10 connections:

A 90.9× difference in space, for representing the exact same graph — because real-world graphs like social networks are sparse: each user connects to a tiny fraction of all other users, not roughly half of them. Chapter 2 formalizes this tradeoff directly, reusing Algorithms & Complexity Chapter 8's own auxiliary-space accounting.

Five Concrete Connections to Real Code

What This Course Won't Cover

Graph theory as a full field is enormous. This course deliberately covers the core representations and the classic named algorithms every working programmer eventually needs, not a comprehensive catalog:

• Specialized algorithms — network flow (max-flow/min-cut), graph coloring, planarity testing, and similar advanced topics stay out of scope; each is substantial enough to deserve its own future treatment
• Graph database technology — this course covers the mathematical structure and algorithms, not specific tools like Neo4j or graph-query languages
• Advanced network flow theory — genuinely deep optimization territory, beyond this course's own scope

Where This Course Is Headed

Hands-On Exercises

Chapter 1 showed the space gap between two representations in the abstract. This chapter builds both, in full, for the exact same small graph — and pins down the vocabulary every later chapter leans on.

Core Terminology

A Worked Example: One Graph, Two Representations

Five vertices, five undirected, unweighted edges: A-B, A-C, B-C, C-D, D-E.

Adjacency Matrix

Adjacency List

Reading degree directly off the adjacency list (its own length per vertex): degree(A)=2, degree(B)=2, degree(C)=3, degree(D)=2, degree(E)=1. For this graph, V=5, E=5: matrix needs 25 cells, the list needs 15 entries — a smaller gap than Chapter 1's own 1,000-vertex example, since the space advantage of the list grows with graph size.

The Time/Space Tradeoff

Representations in Code

Hands-On Exercises

Every algorithm this course covers from here on — cycle detection, topological sort, shortest paths — is a variation on one of two ways to systematically visit every reachable vertex in a graph. Both visit the same vertices in the end; the order they visit them in is what makes each one suited to genuinely different problems.

Breadth-First Search (BFS) — Level by Level

Depth-First Search (DFS) — Follow One Path to the End

A Worked Comparison: Genuinely Different Orders

A branching graph: A connects to B and C; B connects to D and E; C connects to F.

Complexity — And Why the Representation Choice Matters

Real Use Cases

Both Traversals in Code

Hands-On Exercises

Chapter 3 built two ways to explore a graph. This chapter puts them to work answering two genuinely practical questions: is everything actually reachable from everything else, and does this graph loop back on itself somewhere?

Connected Components

A connected component is a maximal group of vertices all reachable from each other. Finding every component in a graph is just Chapter 3's own traversal, repeated: run DFS (or BFS) from any unvisited vertex, mark everything it reaches, then repeat from the next still-unvisited vertex.

A graph with three separate "islands": {A,B,C} (a triangle), {D,E}, {F,G} — no edges connecting the groups.

Cycle Detection in Undirected Graphs

During a DFS, encountering an edge to an already-visited vertex normally signals a cycle — except the edge leading straight back to the vertex you just came from, which is always there in an undirected graph and doesn't count.

Testing two small graphs directly:

Cycle Detection in Directed Graphs — A Genuinely Different Problem

The parent-tracking trick doesn't work for directed graphs — an edge can point to an already-visited vertex without forming a cycle at all, if that vertex was finished processing along a completely different branch. The real signal is a back edge: an edge to a vertex still currently on the DFS call stack, not just visited at some point in the past.

Real Relevance: Detecting Circular Dependencies

Modeling packages as vertices and "depends on" as directed edges — exactly Chapter 1's own dependency-resolution connection:

This is exactly what a real package manager runs before attempting any installation — a directed cycle means the dependency requirements are genuinely impossible to satisfy, not just difficult.

Connectivity & Cycle Detection in Code

Hands-On Exercises

Chapter 4 answered a yes/no question: does this directed graph contain a cycle? When the answer is no — the graph is a DAG (Directed Acyclic Graph) — a much more useful question opens up: what's a valid order to process every vertex in, so that nothing is ever handled before something it depends on?

What a Topological Order Actually Is

A topological sort is a linear ordering of a DAG's vertices such that for every directed edge u → v, u comes before v in the ordering. It only exists for DAGs — Chapter 4's own cycle check is the precondition this chapter builds on. If A → B → A existed, no ordering could ever put both A before B and B before A.

Method 1: DFS-Based — Order by Finish Time, Reversed

Run a DFS exactly like Chapter 4's cycle check, but this time record each vertex the moment it turns black (fully finished — every descendant already processed). Push it onto a stack at that moment. Once the whole DFS is done, popping the stack — i.e. reading it in reverse finish order — is a valid topological order.

Why reverse: a vertex only finishes after all of its descendants have already finished, so it always finishes later than everything it points to — meaning it sits later in the raw finish-order stack. Reversing puts it back in front, ahead of everything it points to. Tracing it directly removes any doubt:

Graph: A→B, A→C, B→C.

Method 2: Kahn's Algorithm — Process What's Ready

Kahn's algorithm works from the opposite direction, and maps much more directly onto how a real scheduler behaves: repeatedly find a vertex with no remaining unprocessed dependencies, output it, then "unlock" whatever becomes newly ready as a result.

Same graph, traced with Kahn's algorithm:

A Topological Order Usually Isn't Unique

When two vertices have no dependency relationship between them at all, either can legally come first. A slightly larger graph makes this visible: A→C, B→C, C→D — both A and B feed independently into C, which feeds into D.

Real Relevance: Build Systems & Package Installation

A compiler deciding which source files to build first, or a package manager deciding install order, is running a topological sort on exactly this kind of dependency DAG. Kahn's own framing maps directly onto the real process: "install everything with no remaining unmet dependencies, then see what that unlocks next" is precisely how tools like npm, pip, and make resolve a build order in practice — and it's the natural next step after Chapter 4's own cycle check, which confirms an order exists at all before this chapter finds one.

Topological Sort in Code

Hands-On Exercises

Every graph so far has been unweighted — Chapter 3's own finding-box already established that BFS finds the shortest path by edge count. Real-world graphs are usually weighted: a road has a distance, a network link has latency, a flight has a price. "Fewest edges" and "cheapest total weight" are genuinely different questions once weights enter the picture, and this chapter builds the algorithm that answers the second one.

Weighted Graphs: One Small Change to the Representation

A weighted graph attaches a number to every edge. The adjacency list from Chapter 2 barely changes — instead of storing just a neighbor, each entry stores a (neighbor, weight) pair: adj['A'] = [('B', 4), ('C', 1)] means A connects to B with weight 4 and to C with weight 1.

Dijkstra's Algorithm: Always Expand the Closest Unfinished Vertex

Dijkstra's algorithm is greedy: it repeatedly finalizes whichever not-yet-finalized vertex currently has the smallest known distance from the source, then uses that vertex to try to improve ("relax") the distances of its neighbors.

Graph: A→B(4), A→C(1), C→B(2), B→D(1), C→D(5), D→E(3). Finding shortest distances from A:

Notice B was updated twice — first to 4 (direct edge from A), then to a cheaper 3 once C was finalized and revealed the shorter route A→C→B. This is the entire point of the greedy strategy: finalize the closest vertex first, because nothing still in the queue can possibly offer it a cheaper route later — every other candidate is already at least as far away.

BFS Was Secretly Dijkstra All Along

Why It Breaks With Negative Weights

Dijkstra's greedy step assumes that once a vertex is finalized, nothing seen later can ever offer it (or anything already routed through it) a cheaper path. A negative edge weight breaks that assumption directly — a big negative edge discovered after a vertex has already been finalized can retroactively make an already-"settled" distance wrong, and Dijkstra never revisits a finalized vertex to fix it.

Graph: A→B(1), A→C(4), C→B(−10), B→D(100).

This is exactly why Dijkstra requires non-negative weights, and exactly the gap Chapter 7's own Bellman-Ford algorithm is built to close.

Real Relevance: Routing & Navigation

GPS and mapping software runs some form of Dijkstra (or a close relative) to find a shortest route by distance or time — road segments as edges, intersections as vertices, travel time or distance as weight. Network routers use a close cousin (OSPF/link-state routing) to find the cheapest path for data by latency and hop cost, with "cheapest" playing the same role weight plays here.

Dijkstra's Algorithm in Code

Hands-On Exercises

Chapter 6 ended with a genuine failure: Dijkstra reported D=101 for a graph where the true shortest distance was 94, because a negative edge corrected a vertex's distance after that vertex had already been greedily finalized. This chapter fixes exactly that failure — with an algorithm that never finalizes anything early enough to get caught out.

The Idea: Stop Trusting Any Distance Until Enough Rounds Have Passed

Where Dijkstra finalizes one vertex at a time and never looks back, Bellman-Ford takes the opposite approach: it relaxes every single edge in the graph, repeatedly, for a fixed number of rounds — giving corrections like the one that broke Dijkstra time to propagate all the way through, no matter how many extra hops away they start.

Why Exactly V − 1 Rounds?

A shortest path that doesn't repeat any vertex (a "simple" path) can use at most V − 1 edges — there are only V vertices to visit at all. Each full round of relaxing every edge guarantees that any shortest path using up to that many edges gets found: round 1 finds every shortest path of 1 edge, round 2 extends those into every shortest path of up to 2 edges, and so on. After V − 1 rounds, every possible simple shortest path — however many edges it needs — has been fully accounted for.

Fixing Chapter 6's Own Counterexample

Same graph that broke Dijkstra: A→B(1), A→C(4), C→B(−10), B→D(100). 4 vertices, so 3 rounds.

The Extra Round: Detecting Negative Cycles

Everything above assumes a shortest simple path exists at all. If the graph contains a negative cycle — a cycle whose total edge weight sums to less than zero — there is no shortest path at all, since going around the cycle again and again keeps reducing the total cost forever. Bellman-Ford detects this directly: run one extra (a V-th) round of relaxation — if any edge can still be relaxed after the normal V−1 rounds finished, a negative cycle reachable from the source must exist.

Graph: A→B(1), B→C(−1), C→A(−1) — a triangle whose total weight is 1 + (−1) + (−1) = −1.

Real Relevance: Currency Arbitrage Detection

This is Bellman-Ford's single most-cited real application: model each currency as a vertex, each exchange rate as an edge weighted −log(rate). A cycle of exchanges is profitable exactly when the product of its rates exceeds 1 — which, because −log turns multiplication into addition, is exactly when the sum of −log(rate) around that cycle is negative. A negative cycle in this graph is a real, mechanically-detectable arbitrage opportunity.

When to Reach for Bellman-Ford Instead of Dijkstra

Bellman-Ford is strictly more capable, but genuinely slower on large graphs — the right default is still Dijkstra whenever negative weights are known to be impossible, reaching for Bellman-Ford specifically when they aren't.

Bellman-Ford in Code

Hands-On Exercises

Chapters 6 and 7 answered "what's the cheapest way from one vertex to the others?" This chapter asks a genuinely different question: given a weighted, undirected, connected graph, what's the cheapest possible way to connect every vertex to every other, using as few edges as it takes and nothing more?

What a Minimum Spanning Tree Actually Is

A spanning tree of a connected graph with V vertices is a subgraph that connects all V vertices using exactly V − 1 edges, with no cycles — precisely the tree definition Chapter 4's own finding-box already established. A Minimum Spanning Tree (MST) is the spanning tree whose edge weights sum to the smallest possible total, out of every spanning tree the graph could have.

Method 1: Kruskal's Algorithm

Sort every edge in the graph by weight, ascending. Go through them one at a time: add an edge to the MST unless both of its endpoints are already connected to each other through edges already added — adding it anyway would create a cycle, which a tree can never have.

Graph: A-B(4), A-C(2), B-C(1), B-D(5), C-D(8), C-E(10), D-E(2), B-E(6).

Method 2: Prim's Algorithm

Start from any single vertex — it's the entire "tree" so far. Repeatedly find the cheapest edge connecting a vertex already in the tree to one that isn't, add that edge and vertex, and repeat until every vertex is included. A priority queue does the "cheapest available edge" lookup, exactly like Dijkstra's own priority queue found the cheapest available distance.

Same graph, starting from A:

Real Relevance: Network Design

Laying fiber or cable to connect a set of offices, data centers, or towns at minimum total cost is precisely the MST problem — vertices are sites, edge weight is the cost of a direct link between two sites, and the MST is the cheapest possible way to make sure every site can reach every other (even if only indirectly, through other sites on the tree). The same shape shows up in circuit board wiring and in clustering algorithms that group data points by cutting the most expensive edges out of an MST.

Kruskal's & Prim's in Code

Hands-On Exercises

Trees have already shown up twice without ever being the main subject — Chapter 4's own finding-box noted that a tree with V vertices has exactly V−1 edges and no cycles, and Chapter 8 built an entire algorithm family around finding one. This chapter finally gives trees their own spotlight: what they're made of, and how the traversal ideas from Chapters 3 and 5 turn out to already be exactly what a tree needs.

A Tree Is Just a Connected, Acyclic Graph

A (free) tree is an undirected graph that is both connected (every vertex reachable from every other) and acyclic (no cycles at all — not even the parent-tracking exception from Chapter 4's undirected cycle check, since a tree has no cycles whatsoever). Any two of the following three properties automatically guarantee the third, for a graph with V vertices:

Rooted Trees: Adding a Direction

A free tree has no designated starting point. Picking one vertex as the root turns it into a rooted tree, which unlocks a whole vocabulary: the root's neighbors become its children, and it becomes their parent; a vertex with no children is a leaf; a vertex's depth is its distance from the root; a tree's height is the greatest depth any vertex reaches; the vertex and everything reachable below it form a subtree.

Worked example, rooted at A: A→{B,C,D}, B→{E,F}, D→{G} (C, E, F, G are leaves).

Traversal Orders: Not New Algorithms, Just Named Moments

A tree has exactly one simple path between any two vertices, so DFS never needs Chapter 4's back-edge check at all — there's nothing to loop back on. On a rooted tree, the only real choice left is when to process ("visit") a node relative to visiting its children:

No new machinery was needed for any of these — pre-order is DFS with no back-edges to worry about, post-order is Chapter 5's finish-order stack read directly instead of reversed (a tree, being acyclic, never needs the reversal that made a topological order valid), and level-order is Chapter 3's BFS applied to a graph that happens to be a tree.

Real Relevance: File Systems, Org Charts & the DOM

A file system is a rooted tree — folders as internal nodes, files as leaves; walking it top-down before descending into each subfolder (exactly how a tool like os.walk or a recursive directory listing behaves) is pre-order traversal. An org chart is a rooted tree of reporting relationships. A web page's DOM is a rooted tree of elements, and a JSON or XML document parses into one too — nested objects and arrays as subtrees. Anywhere a "contains" or "reports to" relationship never loops back on itself, the natural model is a tree, and one of these three traversal orders is almost always the right way to walk it.

Tree Traversal in Code

Hands-On Exercises

One continuous scenario, touching every chapter of this course in the order a real engineer would actually reach for each idea: Nimbus, a small startup, is standing up its own office and infrastructure — and every genuinely different problem that comes up along the way turns out to be a graph problem already covered by this course.

Step 1 — The Office Network: Representation & Connectivity

Step 2 — One Dedicated Line: Cheapest Cable Run to the Server

Step 3 — Wiring Every Room: A Genuinely Different Question

Step 4 — The Deployment Graph: Is the Plan Even Valid?

Step 5 — Request Latency: Where Dijkstra Actually Breaks

Step 6 — The Org Chart, Walked Three Different Ways

What This Course Doesn't Cover

As stated honestly back in Chapter 1: network flow, graph coloring, planarity, and graph-database technology specifically were named as out of scope, and stayed out of scope through all ten chapters. This course built the core representational and algorithmic toolkit — traversal, connectivity, ordering, shortest paths, spanning trees, and tree structure — not an exhaustive catalog of every named graph algorithm.

Where This Course Connects

This course leaned directly on Algorithms & Complexity's own recursion and Big-O machinery throughout — Chapter 1 named this destination explicitly, and Chapters 3 through 8 all reused it for analyzing traversal and shortest-path cost. Discrete Mathematics Fundamentals' own relations material (Chapter 5 there) is the formal ancestor of a graph itself — this course is, in a real sense, what happens when a relation gets a name and a picture. Within Technical Support, netdiag1's own network-troubleshooting material and this course's shortest-path/connectivity chapters describe the same underlying kind of structure from two different angles — one diagnostic, one mathematical.

Hands-On Exercises