Topological Sort

A topological sort is like ordering chores so you always finish the ones that must come first, such as putting on socks before shoes.

In this page:

What is Topological Sort
Indegree
Kahn's Algorithm
Cycle Check
Applications

Syntax

markup

from collections import deque
queue = deque(v for v in graph if indegree[v] == 0)
order = []
while queue:
    node = queue.popleft()
    order.append(node)
    for nxt in graph[node]:
        indegree[nxt] -= 1
        if indegree[nxt] == 0:
            queue.append(nxt)

What is Topological Sort

A topological sort arranges the vertices of a directed acyclic graph in a line so that every edge points from an earlier vertex to a later one — think of it as a valid order to take courses given their prerequisites.

Example: What is Topological Sort

#include <iostream>
using namespace std;
int main() {
	// Courses: 0=Intro, 1=DataStructures(needs 0), 2=Algorithms(needs 1)
	int order[] = {0, 1, 2};
	cout << "Valid order: ";
	for (int c : order) cout << c << " ";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] order = {0, 1, 2};
		System.out.print("Valid order: ");
		for (int c : order) System.out.print(c + " ");
	}
}

order = [0, 1, 2]
print("Valid order:", *order)

#include <stdio.h>
int main() {
	int order[] = {0, 1, 2};
	printf("Valid order: ");
	for (int i = 0; i < 3; i++) printf("%d ", order[i]);
	return 0;
}

Indegree

A vertex's indegree counts how many edges point into it, which is exactly the number of prerequisites that still need to be satisfied before that vertex can safely appear in the ordering.

Example: Indegree

#include <iostream>
using namespace std;
int main() {
	int indegree[3] = {0, 1, 1};
	cout << "Vertex 1 needs " << indegree[1] << " prerequisite(s) satisfied first";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] indegree = {0, 1, 1};
		System.out.println("Vertex 1 needs " + indegree[1] + " prerequisite(s) satisfied first");
	}
}

indegree = [0, 1, 1]
print(f"Vertex 1 needs {indegree[1]} prerequisite(s) satisfied first")

#include <stdio.h>
int main() {
	int indegree[3] = {0, 1, 1};
	printf("Vertex 1 needs %d prerequisite(s) satisfied first", indegree[1]);
	return 0;
}

Kahn's Algorithm

Kahn's algorithm repeatedly removes a vertex with indegree zero (nothing left blocking it), adds it to the output, and decreases the indegree of its neighbors, using a queue to hold all currently-available vertices.

Example: Kahn's Algorithm

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
	vector<vector<int>> adj = {{1},{2},{}};
	vector<int> indegree = {0,1,1};
	queue<int> q; vector<int> output;
	for (int i = 0; i < 3; i++) if (indegree[i] == 0) q.push(i);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		output.push_back(u);
		for (int v : adj[u]) if (--indegree[v] == 0) q.push(v);
	}
	for (int v : output) cout << v << " ";
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		List<List<Integer>> adj = Arrays.asList(Arrays.asList(1), Arrays.asList(2), Arrays.asList());
		int[] indegree = {0,1,1};
		Queue<Integer> q = new LinkedList<>();
		List<Integer> output = new ArrayList<>();
		for (int i = 0; i < 3; i++) if (indegree[i] == 0) q.add(i);
		while (!q.isEmpty()) {
			int u = q.poll();
			output.add(u);
			for (int v : adj.get(u)) if (--indegree[v] == 0) q.add(v);
		}
		System.out.println(output);
	}
}

from collections import deque
adj = [[1],[2],[]]
indegree = [0,1,1]
q = deque(i for i in range(3) if indegree[i] == 0)
output = []
while q:
    u = q.popleft()
    output.append(u)
    for v in adj[u]:
        indegree[v] -= 1
        if indegree[v] == 0:
            q.append(v)
print(*output)

#include <stdio.h>
int main() {
	int adj[3][1] = {{1},{2},{-1}};
	int indegree[3] = {0,1,1}, queue[3], front=0, back=0, output[3], n=0;
	for (int i = 0; i < 3; i++) if (indegree[i] == 0) queue[back++] = i;
	while (front < back) {
		int u = queue[front++];
		output[n++] = u;
		if (adj[u][0] != -1 && --indegree[adj[u][0]] == 0) queue[back++] = adj[u][0];
	}
	for (int i = 0; i < n; i++) printf("%d ", output[i]);
	return 0;
}

Cycle Check

If the algorithm finishes without having placed every vertex, some vertices' indegrees never dropped to zero — meaning they're stuck in a cycle, so a topological order simply cannot exist for that graph.

Example: Cycle Check

#include <iostream>
using namespace std;
int main() {
	int placed = 2, total = 3;
	if (placed < total) cout << "Only " << placed << "/" << total << " placed: remaining vertices stuck in a cycle";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int placed = 2, total = 3;
		if (placed < total) System.out.println("Only " + placed + "/" + total + " placed: remaining vertices stuck in a cycle");
	}
}

placed, total = 2, 3
if placed < total:
    print(f"Only {placed}/{total} placed: remaining vertices stuck in a cycle")

#include <stdio.h>
int main() {
	int placed = 2, total = 3;
	if (placed < total) printf("Only %d/%d placed: remaining vertices stuck in a cycle", placed, total);
	return 0;
}

Applications

Build systems use topological order to compile files only after their dependencies, and course-scheduling systems use it to find a legal sequence of classes that respects every prerequisite.

Example: Applications

#include <iostream>
using namespace std;
int main() {
	cout << "Build systems compile files after dependencies; scheduling finds a legal class sequence";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Build systems compile files after dependencies; scheduling finds a legal class sequence");
	}
}

print("Build systems compile files after dependencies; scheduling finds a legal class sequence")

#include <stdio.h>
int main() {
	printf("Build systems compile files after dependencies; scheduling finds a legal class sequence");
	return 0;
}

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Cycle Detection Next Lesson → Shortest Path Dijkstra