Chapter 8: Advanced Graphs
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.
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
Topological Sort
Linear ordering of a DAG so every edge points forward — via Kahn's BFS or reverse DFS postorder.
Task Scheduling
Cycle detection and Course Schedule — topological sort's most famous application.
Alien Dictionary
Extract character ordering from sorted words — build a DAG, then topo-sort it.
Dijkstra's Algorithm
Greedy shortest path in weighted graphs — priority queue + edge relaxation.
Minimum Spanning Tree
Connect all nodes at minimum cost — Kruskal with Union-Find or Prim with a heap.
A topological sort of a directed acyclic graph (DAG) produces a linear ordering of its vertices such that for every directed edge , vertex appears before vertex in the ordering. This ordering is only possible if the graph has no cycles --- hence the requirement that the graph be a DAG.
There are two classic approaches: Kahn's algorithm (BFS-based, using in-degree tracking) and a DFS-based method that appends nodes to the result in reverse finishing order. Both run in time.
In this topic
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 vertices, the ordering is valid. If fewer than vertices are processed, the graph contains a cycle and no topological order exists.
Time: --- each vertex and edge processed once. Space: for the queue and in-degree array.
Kahn's algorithm produces a topological order by repeatedly removing vertices with in-degree 0. Start by computing in-degrees in , enqueue all zero-in-degree vertices, then repeatedly dequeue , append to result, and decrement in-degrees of 's successors; enqueue any that drop to 0. Total time is because each edge is processed once (decrement) and each vertex is enqueued/dequeued once. If the final result has fewer than vertices, the graph has a cycle — Kahn's naturally detects this.
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.
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: . Space: for the recursion stack and visited set.
DFS-based topo sort computes the postorder of a DFS traversal, then reverses it. The key insight: when DFS finishes processing a vertex (all descendants done), 's postorder timestamp is later than all its descendants'. Reversing puts before its descendants, which is exactly the topological requirement. Time is . 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.
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.