Topological Sort
In this page:
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 10 topics to unlock
0/10 topics done
Complete these topics first: