Topological Sort
Linear ordering of vertices in a DAG such that every directed edge u→v has u before v. The foundation of dependency resolution, course scheduling, and build systems.
The Pattern
Topological sort only applies to directed acyclic graphs (DAGs). There are two equivalent algorithms:
Kahn's algorithm (BFS): Maintain a queue of nodes with in-degree 0. Process one at a time; after processing a node, decrement the in-degree of its neighbors. Nodes whose in-degree reaches 0 join the queue. If all nodes are processed, the graph is a DAG and the processing order is a valid topological sort. If any node is left unprocessed, there is a cycle.
DFS-based: Run DFS. When a node's DFS finishes (all descendants are processed), push the node onto a stack. After all DFS calls, the stack's top-to-bottom is a valid topological order. Cycle detection requires tracking nodes currently in the DFS call stack (grey nodes).
Kahn's is easier to implement and cycle-detection falls out naturally, so most interview problems use it.
Course Schedule I — Can All Courses Be Finished?
Given n courses (0 to n-1) and prerequisites[i] = [a, b] meaning "b must be taken before a", determine if all courses can be finished. This is equivalent to checking if the prerequisite graph is a DAG.
fn can_finish(num_courses: usize, prerequisites: &[[usize; 2]]) -> bool {
let mut in_degree = vec![0usize; num_courses];
let mut adj: Vec<Vec<usize>> = vec![Vec::new(); num_courses];
for &[a, b] in prerequisites {
adj[b].push(a);
in_degree[a] += 1;
}
let mut queue: std::collections::VecDeque<usize> =
(0..num_courses).filter(|&i| in_degree[i] == 0).collect();
let mut processed = 0;
while let Some(node) = queue.pop_front() {
processed += 1;
for &nb in &adj[node] {
in_degree[nb] -= 1;
if in_degree[nb] == 0 { queue.push_back(nb); }
}
}
processed == num_courses
}
fn main() {
println!("{}", can_finish(2, &[[1,0]])); // true (0→1, no cycle)
println!("{}", can_finish(2, &[[1,0],[0,1]])); // false (cycle)
println!("{}", can_finish(4, &[[1,0],[2,0],[3,1],[3,2]])); // true
}Course Schedule II — Return the Order
Return one valid ordering of courses, or an empty vector if impossible. The processing order in Kahn's algorithm is the topological order.
fn find_order(num_courses: usize, prerequisites: &[[usize; 2]]) -> Vec<usize> {
let mut in_degree = vec![0usize; num_courses];
let mut adj: Vec<Vec<usize>> = vec![Vec::new(); num_courses];
for &[a, b] in prerequisites {
adj[b].push(a);
in_degree[a] += 1;
}
let mut queue: std::collections::VecDeque<usize> =
(0..num_courses).filter(|&i| in_degree[i] == 0).collect();
let mut order = Vec::new();
while let Some(node) = queue.pop_front() {
order.push(node);
for &nb in &adj[node] {
in_degree[nb] -= 1;
if in_degree[nb] == 0 { queue.push_back(nb); }
}
}
if order.len() == num_courses { order } else { vec![] }
}
fn main() {
println!("{:?}", find_order(2, &[[1,0]])); // [0, 1]
println!("{:?}", find_order(4, &[[1,0],[2,0],[3,1],[3,2]])); // [0,1,2,3] or [0,2,1,3]
println!("{:?}", find_order(2, &[[1,0],[0,1]])); // [] (cycle)
}Alien Dictionary — Derive Character Order from Sorted Words
Given a list of words sorted in an alien language's alphabetical order, derive the order of characters. Compare adjacent words to extract ordering constraints (the first differing character gives one edge). Then topological sort the characters.
use std::collections::{HashMap, HashSet, VecDeque};
fn alien_order(words: &[&str]) -> String {
// Collect all unique characters
let mut in_degree: HashMap<char, usize> = HashMap::new();
let mut adj: HashMap<char, Vec<char>> = HashMap::new();
for word in words {
for ch in word.chars() {
in_degree.entry(ch).or_insert(0);
adj.entry(ch).or_default();
}
}
// Compare adjacent pairs to get ordering edges
for pair in words.windows(2) {
let (w1, w2) = (pair[0], pair[1]);
let chars1: Vec<char> = w1.chars().collect();
let chars2: Vec<char> = w2.chars().collect();
let min_len = chars1.len().min(chars2.len());
// Invalid: longer word is prefix of shorter — no valid order
if chars1.len() > chars2.len() && w1.starts_with(w2) { return String::new(); }
for i in 0..min_len {
if chars1[i] != chars2[i] {
adj.get_mut(&chars1[i]).unwrap().push(chars2[i]);
*in_degree.entry(chars2[i]).or_insert(0) += 1;
break;
}
}
}
// Kahn's topological sort
let mut queue: VecDeque<char> = in_degree.iter()
.filter(|&(_, &d)| d == 0)
.map(|(&c, _)| c)
.collect();
let mut result = String::new();
while let Some(ch) = queue.pop_front() {
result.push(ch);
if let Some(neighbors) = adj.get(&ch) {
for &nb in neighbors {
let d = in_degree.get_mut(&nb).unwrap();
*d -= 1;
if *d == 0 { queue.push_back(nb); }
}
}
}
if result.len() == in_degree.len() { result } else { String::new() }
}
fn main() {
// ["wrt","wrf","er","ett","rftt"]
// w < e, r < t, t < f, e < r → "wertf"
println!("{}", alien_order(&["wrt","wrf","er","ett","rftt"])); // "wertf"
println!("{}", alien_order(&["z","x"])); // "zx"
println!("{}", alien_order(&["z","x","z"])); // "" (cycle)
}Sequence Reconstruction — Unique Topological Order
Check if a target sequence org is the only shortest supersequence that can be reconstructed from sequences in seqs. The sequence is uniquely reconstructable if and only if the topological sort has exactly one valid order, which means the queue never has more than one node at a time.
fn sequence_reconstruction(org: &[i32], seqs: &[Vec<i32>]) -> bool {
use std::collections::{HashMap, VecDeque};
let n = org.len();
let mut in_degree: HashMap<i32, usize> = HashMap::new();
let mut adj: HashMap<i32, Vec<i32>> = HashMap::new();
for &v in org {
in_degree.entry(v).or_insert(0);
adj.entry(v).or_default();
}
for seq in seqs {
for &v in seq { in_degree.entry(v).or_insert(0); }
for pair in seq.windows(2) {
let (a, b) = (pair[0], pair[1]);
adj.entry(a).or_default().push(b);
*in_degree.entry(b).or_insert(0) += 1;
}
}
if in_degree.len() != n { return false; }
let mut queue: VecDeque<i32> = in_degree.iter()
.filter(|&(_, &d)| d == 0)
.map(|(&v, _)| v)
.collect();
let mut order = Vec::new();
while let Some(node) = queue.pop_front() {
if queue.len() > 0 { return false; } // not unique
order.push(node);
for &nb in adj.get(&node).unwrap_or(&vec![]) {
let d = in_degree.get_mut(&nb).unwrap();
*d -= 1;
if *d == 0 { queue.push_back(nb); }
}
}
order == org
}
fn main() {
println!("{}", sequence_reconstruction(
&[1,2,3],
&[vec![1,2], vec![1,3], vec![2,3]]
)); // true
println!("{}", sequence_reconstruction(
&[1,2,3],
&[vec![1,2], vec![2,3], vec![3,1]]
)); // false (cycle)
println!("{}", sequence_reconstruction(
&[4,1,5,2,6,3],
&[vec![5,2,6,3], vec![4,1,5,2]]
)); // true
}Build Order — Tasks with Dependencies
Given a list of tasks and dependencies, produce a build order. A project build system (Make, Gradle, CMake) solves exactly this at startup. The output is Kahn's processing order.
fn build_order(tasks: &[&str], deps: &[(&str, &str)]) -> Option<Vec<String>> {
use std::collections::{HashMap, VecDeque};
let mut idx: HashMap<&str, usize> = HashMap::new();
for (i, &t) in tasks.iter().enumerate() { idx.insert(t, i); }
let n = tasks.len();
let mut in_degree = vec![0usize; n];
let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
for &(a, b) in deps { // b must come before a
let (ai, bi) = (idx[a], idx[b]);
adj[bi].push(ai);
in_degree[ai] += 1;
}
let mut queue: VecDeque<usize> = (0..n).filter(|&i| in_degree[i] == 0).collect();
let mut order = Vec::new();
while let Some(node) = queue.pop_front() {
order.push(tasks[node].to_string());
for &nb in &adj[node] {
in_degree[nb] -= 1;
if in_degree[nb] == 0 { queue.push_back(nb); }
}
}
if order.len() == n { Some(order) } else { None }
}
fn main() {
let tasks = ["a","b","c","d","e","f"];
let deps = [("d","a"),("b","f"),("d","b"),("a","f"),("c","d")];
match build_order(&tasks, &deps) {
Some(order) => println!("{:?}", order), // valid topological order
None => println!("Cycle detected"),
}
}