Chapter 8: Advanced Graphs

Week 8

Explore advanced graph algorithms including topological sort, shortest paths in weighted graphs, and minimum spanning trees. Master Kahn's algorithm, Dijkstra's algorithm, Kruskal's and Prim's algorithms, and solve classic problems like course scheduling and alien dictionary.

Topics: 5
Demos: 5
Min read: 21

Chapter Overview

Building on the graph fundamentals from the previous chapter, we now tackle algorithms that exploit special graph structures --- directed acyclic graphs (DAGs), weighted edges, and global optimization over all edges.

These algorithms power real-world systems: build systems use topological sort to determine compilation order, GPS navigation uses Dijkstra's algorithm to find the fastest route, and network design uses minimum spanning trees to minimize wiring costs.

This chapter covers five key areas:

Topological Sort: Ordering vertices in a DAG so every edge points forward
Task Scheduling: Detecting whether a set of tasks with prerequisites can be completed
Alien Dictionary: Reconstructing an unknown ordering from sorted data
Dijkstra's Algorithm: Finding shortest paths in graphs with non-negative edge weights
Minimum Spanning Tree: Connecting all vertices with minimum total edge weight

Chapter Roadmap

Click any topic to jump in

Interactive demo

Topological Sort

Linear ordering of a DAG so every edge points forward — via Kahn's BFS or reverse DFS postorder.

Kahn's Algorithm (BFS-Based)DFS-Based Topological Sort

Scheduling and cycle detection

Task Scheduling

Cycle detection and Course Schedule — topological sort's most famous application.

Cycle Detection in Directed GraphsCourse Schedule Ordering

Ordering problems across domains

Alien Dictionary

Extract character ordering from sorted words — build a DAG, then topo-sort it.

Extracting Ordering from Sorted WordsBuilding and Sorting the Character DAG

From unweighted to weighted

Dijkstra's Algorithm

Greedy shortest path in weighted graphs — priority queue + edge relaxation.

Relaxation and the Priority QueuePath Reconstruction

Optimal spanning structures

Minimum Spanning Tree

Connect all nodes at minimum cost — Kruskal with Union-Find or Prim with a heap.

Kruskal's Algorithm with Union-FindPrim's Algorithm

Topics

5 topics in this chapter

A build system must compile a library before every program that imports it, a spreadsheet must recompute a cell before every formula that reads it, and a package manager must install dependencies before the packages that need them. Each problem is a set of tasks plus "must come before" rules, and the question is the same: in what order can the tasks run so that no task starts before its prerequisites?

The previous chapter, Graphs, ended with Word Ladder, a BFS over an undirected implicit graph. Ordering problems need directed edges: an edge $u \to v$ means $u$ must come before $v$ . A topological sort lists the vertices so that every edge points forward. Such an order exists exactly when the graph has no directed cycle, a directed acyclic graph or DAG, because a cycle would require a task to come before itself.

We first build Kahn's algorithm, which repeatedly removes a vertex that no remaining edge points into, using in-degree counts and a queue. Then we derive the DFS method, which lists vertices in reverse order of when their searches finish, and compare what each approach reveals when the graph does contain a cycle.

Definition

A topological sort of a directed graph $G = (V, E)$ is a linear ordering of its vertices such that for every edge $u \to v$ , $u$ comes before $v$ . It exists if and only if $G$ is acyclic, and is usually not unique. Kahn's algorithm and DFS finishing order each compute one in $O(V + E)$ time.

In this topic

1Kahn's Algorithm (BFS-Based)
2DFS-Based Topological Sort

1 of 2

Kahn's Algorithm (BFS-Based)

Kahn's algorithm works by repeatedly removing vertices with in-degree 0 (no incoming edges). Start by computing the in-degree of every vertex. Add all vertices with in-degree 0 to a queue. Process each vertex from the queue: add it to the result, then decrement the in-degree of all its neighbors. If a neighbor's in-degree drops to 0, enqueue it.

If the result contains all $V$ vertices, the ordering is valid. If fewer than $V$ vertices are processed, the graph contains a cycle and no topological order exists.

Time: $O(V + E)$ --- each vertex and edge processed once. Space: $O(V)$ for the queue and in-degree array.

Mathematical Intuition

Kahn's algorithm produces a topological order by repeatedly removing vertices with in-degree 0. Start by computing in-degrees in $O(V + E)$ , enqueue all zero-in-degree vertices, then repeatedly dequeue $u$ , append to result, and decrement in-degrees of $u$ 's successors; enqueue any that drop to 0. Total time is $O(V + E)$ because each edge is processed once (decrement) and each vertex is enqueued/dequeued once. If the final result has fewer than $V$ vertices, the graph has a cycle — Kahn's naturally detects this.

Example:

Given a DAG with edges: 5->0, 5->2, 4->0, 4->1, 2->3, 3->1. Find a topological ordering using Kahn's algorithm.

2 of 2

DFS-Based Topological Sort

The DFS approach performs a depth-first traversal and records each vertex's finish time. When a DFS call finishes processing a vertex (all descendants explored), the vertex is pushed onto a stack (or prepended to a list). The final stack order, read top to bottom, is a valid topological sort.

The intuition is that a vertex finishes after all vertices it can reach have finished --- so it belongs earlier in the ordering. This method naturally handles disconnected DAGs by running DFS from each unvisited vertex.

Time: $O(V + E)$ . Space: $O(V)$ for the recursion stack and visited set.

Mathematical Intuition

DFS-based topo sort computes the postorder of a DFS traversal, then reverses it. The key insight: when DFS finishes processing a vertex $u$ (all descendants done), $u$ 's postorder timestamp is later than all its descendants'. Reversing puts $u$ before its descendants, which is exactly the topological requirement. Time is $O(V + E)$ . To detect cycles, track vertices in three states: white (unvisited), gray (on stack), black (finished). Encountering a gray vertex means a back edge — a cycle.

Example:

Run DFS-based topological sort on the same graph: 5->0, 5->2, 4->0, 4->1, 2->3, 3->1. Start DFS from vertex 5, then 4.

Papers

Kahn, A. B. — Topological Sorting of Large Networks (1962, Communications of the ACM)Tarjan, R. E. — Edge-Disjoint Spanning Trees and Depth-First Search (1976, Acta Informatica)

Blogs

Topological Sorting — CP-Algorithms Topological Sorting — GeeksforGeeks

Definition

Task scheduling with prerequisites models tasks as vertices and each requirement "a before b" as a directed edge $a \to b$ . All tasks can be completed if and only if the graph has no directed cycle; any topological order is then a valid schedule, and with unlimited parallelism the minimum number of rounds equals the number of vertices on the longest path.

In this topic

1Cycle Detection in Directed Graphs
2Course Schedule Ordering

1 of 2

Cycle Detection in Directed Graphs

A directed graph has a cycle if and only if a DFS encounters a back edge --- an edge from a vertex to one of its ancestors in the current DFS tree. We track three states for each vertex: unvisited, in the current recursion stack (active), and fully processed.

Alternatively, Kahn's algorithm detects cycles implicitly: if the topological sort result contains fewer than $V$ vertices, the remaining vertices form one or more cycles.

Key insight: Undirected cycle detection only needs a visited set, but directed cycle detection requires distinguishing between "currently being explored" and "fully finished" nodes.

Mathematical Intuition

A directed graph has a cycle iff DFS encounters a 'back edge' — an edge to an ancestor in the DFS tree (a gray vertex). Equivalently, Kahn's algorithm terminates with fewer than $V$ outputs. Both methods run in $O(V + E)$ . The handshaking analog for DAGs: any DAG on $n$ vertices has at least one source (in-degree 0) and at least one sink (out-degree 0), because a cycle-free graph must have a vertex with no incoming edges — otherwise we could walk backward forever.

Example:

There are 4 courses (0-3) with prerequisites: [1,0], [2,1], [3,2], [1,3] (meaning to take course 1 you need course 0, etc.). Can all courses be finished?

2 of 2

Course Schedule Ordering

The extended version asks not just whether all courses can be completed, but to return a valid ordering. This is exactly the topological sort of the prerequisite graph. If no cycle exists, any topological ordering is a valid course schedule.

Common variations include:

Course Schedule I: Return true/false (cycle detection only)
Course Schedule II: Return a valid ordering or empty if impossible
Minimum semesters: Find the minimum number of semesters to complete all courses (longest path in the DAG, equivalent to BFS level count)

Mathematical Intuition

The Course Schedule problem asks: given prerequisites as directed edges $\text{prereq} \to \text{course}$ , produce a valid ordering or report impossibility. This is exactly topological sort. Using Kahn's: enqueue courses with no prerequisites, then remove them one at a time, decrementing downstream in-degrees. Output order is a valid schedule. Total time $O(V + E) = O(\text{courses} + \text{prereqs})$ . If the output length $< V$ , a prerequisite cycle exists and no valid schedule is possible.

Example:

4 courses with prerequisites: [1,0], [2,0], [3,1], [3,2]. Find a valid ordering and the minimum number of semesters (taking as many courses in parallel as possible).

Papers

Kelley, J. E. — Critical-Path Planning and Scheduling: Mathematical Basis (1961, Operations Research)Kahn, A. B. — Topological Sorting of Large Networks (1962, Communications of the ACM)

Blogs

Course Schedule — LeetCode Editorial Course Schedule II — NeetCode

Definition

Alien Dictionary gives words sorted in an unknown alphabet and asks for a letter order consistent with them. Each adjacent pair contributes at most one edge, from the earlier word's letter to the later word's letter at their first differing position. A topological sort of these edges, over all letters present, is an answer; a cycle or a longer word before its own prefix makes the input invalid.

In this topic

1Extracting Ordering from Sorted Words
2Building and Sorting the Character DAG

1 of 2

Extracting Ordering from Sorted Words

Given a sorted list of alien words, compare each consecutive pair character by character. The first differing position reveals an ordering: the character from the earlier word comes before the character from the later word. Characters at matching positions provide no ordering information.

Edge case: If word A is a prefix of word B and A comes first, no new edge is extracted (this is consistent). But if B is a prefix of A and B comes first, the input is invalid --- a shorter word cannot come after its prefix in any valid ordering.

Time: $O(C)$ total where $C$ is the sum of all character lengths, since each character is compared at most once.

Mathematical Intuition

Given words in alien dictionary order, adjacent pairs $(w_i, w_{i+1})$ reveal one ordering constraint: the first position where they differ. If $w_i = \text{ab}$ and $w_{i+1} = \text{ad}$ , then $b < d$ in the alien order. This gives at most $n-1$ edges from $n$ words. Edge case: if $w_i$ is a prefix of $w_{i+1}$ , no constraint is extracted; but if $w_{i+1}$ is a proper prefix of $w_i$ (e.g., abc before ab), the input is invalid since lexicographic order would require the shorter one first.

Example:

Given sorted alien words: ["wrt", "wrf", "er", "ett", "rftt"]. Extract ordering edges.

2 of 2

Building and Sorting the Character DAG

After extracting all ordering edges, build a directed graph where vertices are characters and edges represent "comes before" relationships. Run topological sort to produce the alien alphabet.

Important details:

All unique characters must appear in the result, even if they have no ordering edges.
If the topological sort detects a cycle, the input is inconsistent and no valid ordering exists.
Multiple valid orderings may exist (the problem typically asks for any one valid ordering).
Characters that appear in the words but have no ordering constraints can be placed anywhere in the result.

Mathematical Intuition

Build a directed graph with all unique characters as vertices and extracted constraints as edges, then topologically sort. With at most 26 characters and $n-1$ edges, $V \leq 26$ and $E \leq n-1$ , so Kahn's algorithm runs in $O(V + E) = O(n)$ . If the result is not a valid topological order (cycle detected), the alien dictionary is inconsistent. Multiple valid orderings can exist — Kahn's arbitrarily picks one based on queue processing order, which may depend on initial vertex insertion order.

Example:

From edges t->f, w->e, r->t, e->r, find the alien alphabet order.

Papers

Kahn, A. B. — Topological Sorting of Large Networks (1962, Communications of the ACM)

Blogs

Alien Dictionary — NeetCode Given a Sorted Dictionary of an Alien Language — GeeksforGeeks

Definition

Dijkstra's algorithm computes shortest-path distances from a source $s$ to every vertex of a graph with non-negative edge weights. It repeatedly removes the unsettled vertex $u$ with the smallest tentative distance from a min-heap, fixes that distance, and relaxes each edge $(u, v)$ of weight $w$ by setting dist[v] to dist[u] + w when that is smaller. With a binary heap it runs in $O((V + E) \log V)$ time.

In this topic

1Relaxation and the Priority Queue
2Path Reconstruction

1 of 2

Relaxation and the Priority Queue

Relaxation is the core operation: for an edge $(u, v)$ with weight $w$ , if $\text{dist}[u] + w < \text{dist}[v]$ , then update $\text{dist}[v] = \text{dist}[u] + w$ . This means we found a shorter path to $v$ through $u$ .

A min-heap (priority queue) always gives us the unprocessed vertex closest to the source. Once a vertex is extracted from the heap, its distance is final --- no future relaxation can improve it (this is guaranteed by non-negative weights).

Time: $O((V + E) \log V)$ with a binary heap. Space: $O(V)$ for distances plus $O(V + E)$ for the graph.

Mathematical Intuition

Dijkstra's algorithm maintains $\text{dist}[v]$ , an upper bound on the shortest-path distance from source $s$ to $v$ , initially $\text{dist}[s] = 0$ and $\infty$ elsewhere. It repeatedly extracts the vertex $u$ with minimum tentative distance and 'relaxes' each outgoing edge: if $\text{dist}[u] + w(u, v) < \text{dist}[v]$ , update $\text{dist}[v]$ and push $v$ onto the priority queue. Using a binary heap, time is $O((V + E) \log V)$ . The invariant: when $u$ is extracted, $\text{dist}[u]$ is finalized — the greedy choice works because edge weights are non-negative.

Example:

Graph with edges: A->B (weight 4), A->C (weight 1), C->B (weight 2), B->D (weight 1), C->D (weight 5). Find shortest paths from A.

2 of 2

Path Reconstruction

Finding shortest distances is useful, but often we need the actual path. During relaxation, whenever we update $\text{dist}[v]$ , we also record $\text{prev}[v] = u$ --- the vertex that led to this improvement. After the algorithm finishes, we reconstruct the path by following the prev pointers backward from the destination to the source.

Why Dijkstra fails with negative weights: The algorithm's correctness relies on the invariant that once a vertex is extracted from the heap, its distance is final. Negative edges can violate this --- a vertex processed later might offer a cheaper path through a negative edge to an already-finalized vertex.

Mathematical Intuition

Like BFS, Dijkstra tracks predecessors: when relaxing $(u, v)$ successfully, set $\text{prev}[v] = u$ . To reconstruct the shortest path to target $t$ , walk backward $t \to \text{prev}[t] \to \cdots \to s$ and reverse. This adds $O(V)$ space for the predecessor map. For multiple shortest paths (ties), prev stores only one, giving any single optimal path. Enumerating all shortest paths requires storing all predecessors per vertex — exponential in the worst case.

Example:

Using the previous graph, reconstruct the shortest path from A to D.

Papers

Dijkstra, E. W. — A Note on Two Problems in Connexion with Graphs (1959, Numerische Mathematik)Fredman, M. L. & Tarjan, R. E. — Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms (1987, Journal of the ACM)

Blogs

Dijkstra's Algorithm — CP-Algorithms Dijkstra's Shortest Path Algorithm — GeeksforGeeks

Definition

A minimum spanning tree of a connected, undirected, weighted graph is a subset of $V - 1$ edges that connects every vertex without forming a cycle and has the smallest possible total weight. Kruskal's algorithm finds one in $O(E \log E)$ time with sorting and Union-Find; Prim's algorithm finds one in $O((V + E) \log V)$ time with a binary heap.

In this topic

1Kruskal's Algorithm with Union-Find
2Prim's Algorithm

1 of 2

Kruskal's Algorithm with Union-Find

Kruskal's algorithm sorts all edges by weight and processes them in ascending order. For each edge, if it connects two vertices that are not already connected (in different components), add it to the MST. Otherwise, skip it (it would create a cycle).

The Union-Find (Disjoint Set Union) data structure efficiently tracks connected components. It supports two operations:

Find(x): Return the root/representative of x's component (with path compression)
Union(x, y): Merge the components containing x and y (with rank-based merging)

Time: $O(E \log E)$ dominated by sorting. Union-Find operations are nearly $O(1)$ amortized.

Mathematical Intuition

Kruskal's builds an MST by considering edges in non-decreasing weight order and adding each edge that does not form a cycle. Union-Find (disjoint-set union) with path compression and union-by-rank supports find and union in near-constant amortized time — formally $O(\alpha(V))$ where $\alpha$ is the inverse Ackermann function, at most 4 for any realistic input. Total time is $O(E \log E)$ dominated by the sort. Correctness follows from the cut property: the minimum-weight edge crossing any cut is in some MST.

Example:

Graph with edges: A-B(4), A-C(2), B-C(1), B-D(5), C-D(8), C-E(10), D-E(2). Find the MST using Kruskal's.

2 of 2

Prim's Algorithm

Prim's algorithm grows the MST from a single starting vertex. Maintain a set of vertices already in the MST. At each step, add the cheapest edge that connects a vertex in the MST to a vertex outside it. Repeat until all vertices are included.

Using a min-heap, Prim's runs in $O((V + E) \log V)$ --- the same complexity as Dijkstra. In fact, Prim's is structurally similar to Dijkstra, but instead of tracking shortest distance from source, it tracks the minimum edge weight to connect to the growing tree.

Prim's vs Kruskal's: Prim's is better for dense graphs (adjacency matrix, $O(V^2)$ without heap). Kruskal's is better for sparse graphs and when edges are already sorted.

Mathematical Intuition

Prim's grows the MST from a single vertex by repeatedly adding the minimum-weight edge that connects the current tree to a new vertex. With a binary heap, time is $O((V + E) \log V)$ ; with a Fibonacci heap, $O(E + V \log V)$ . Each vertex enters the heap once, and each edge may trigger a decrease-key. Correctness also follows from the cut property. Prim's is preferred on dense graphs ( $E \approx V^2$ ) where its work scales with $E$ ; Kruskal's is preferred on sparse graphs where sorting dominates.

Example:

Same graph: A-B(4), A-C(2), B-C(1), B-D(5), C-D(8), C-E(10), D-E(2). Find MST using Prim's starting from A.

Papers

Kruskal, J. B. — On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem (1956, Proceedings of the AMS)Prim, R. C. — Shortest Connection Networks and Some Generalizations (1957, Bell System Technical Journal)

Blogs

Minimum Spanning Tree — CP-Algorithms Kruskal's Minimum Spanning Tree Algorithm — GeeksforGeeks

Chapter 8: Advanced Graphs

Chapter Overview

Chapter Roadmap

Topological Sort

Task Scheduling

Alien Dictionary

Dijkstra's Algorithm

Minimum Spanning Tree

5 topics in this chapter

Topological Sort

Definition

In this topic

Kahn's Algorithm (BFS-Based)

DFS-Based Topological Sort

Related Problems on PixelBank

Task Scheduling

Definition

In this topic

Cycle Detection in Directed Graphs

Course Schedule Ordering

Related Problems on PixelBank

Alien Dictionary

Definition

In this topic

Extracting Ordering from Sorted Words

Building and Sorting the Character DAG

Related Problems on PixelBank

Dijkstra's Algorithm

Definition

In this topic

Relaxation and the Priority Queue

Path Reconstruction

Related Problems on PixelBank

Minimum Spanning Tree

Definition

In this topic

Kruskal's Algorithm with Union-Find

Prim's Algorithm