Topological Sort using Source Removal (Kahn's Algorithm) solves the Topological Sort problem for directed acyclic graphs (DAGs).
Topological sorting produces a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge \((u, v)\), vertex \(u\) appears before vertex \(v\) in the ordering. The source removal approach is classified under Decrease-and-Conquer because it systematically reduces the problem size by repeatedly removing vertices with no incoming edges (sources) until the graph is empty.
The source removal algorithm exemplifies the decrease-and-conquer paradigm in several key ways:
A vertex with in-degree 0 (a source) has no prerequisites and can safely be placed next in the topological ordering. After placing a source in the output, we "remove" it and all its outgoing edges, potentially creating new sources. This process continues until either all vertices are processed (successful topological sort) or we reach a state with no sources but remaining vertices (indicating a cycle).
Consider this example DAG showing the source removal process:
The algorithm maintains a queue of source vertices and processes them iteratively:
topologicalSort()
n be the number of vertices in the graph.inDegree[0..n−1] = 0queue = emptyresult = empty list(u, v): increment inDegree[v]v: if inDegree[v] = 0, enqueue vqueue is not empty:
uu to resultv of u:
inDegree[v]inDegree[v] = 0, enqueue vresult.size() = n, return result▶ In-Degree Tracking: Instead of using DFS traversal, the algorithm explicitly computes and maintains in-degree counts for each vertex, directly identifying sources (vertices with in-degree 0).
▶ Queue-Based Processing: Uses a queue to process sources in a breadth-first manner, rather than the depth-first recursive approach. This makes the algorithm naturally iterative.
▶ Cycle Detection by Counting: Detects cycles by checking if all vertices were processed. If fewer than n vertices are output, remaining vertices must be part of cycles (no sources left but vertices remain).
Why This Works: At each step, removing sources and their edges cannot create new cycles—it only removes dependencies. If the graph is acyclic, this process will eventually eliminate all vertices. If cycles exist, we'll reach a state where no sources remain but vertices still exist, indicating the presence of cycles.
The demo below shows the source removal process and cycle detection capabilities:
The source removal approach produces a topological ordering by:
Unlike DFS-based approaches that require post-processing (sorting by finish time or stack reversal), source removal directly constructs the topological order during execution.
These implementations show the source removal (Kahn's algorithm) approach using in-degree counting and queue-based processing.
Implementation Notes:
List<Integer>[] array of lists for graph representationQueue<Integer> for processing sourcesArrayList<> for final topological orderingvector<int> adj[] array of vectors for graph representationqueue<int> for processing sourcesvector<int> for final topological orderingadj for graph representationcollections.deque for efficient queue operationslist for final topological orderingList<Integer> topologicalSort(List<Integer>[] adj, int n) {
int[] inDegree = new int[n];
// Calculate in-degrees
for (int v = 0; v < n; v++) {
for (int u : adj[v]) {
inDegree[u]++;
}
}
// Initialize queue with sources
Queue<Integer> queue = new LinkedList<>();
for (int v = 0; v < n; v++) {
if (inDegree[v] == 0) {
queue.offer(v);
}
}
List<Integer> result = new ArrayList<>();
// Process sources iteratively
while (!queue.isEmpty()) {
int u = queue.poll();
result.add(u);
// Remove u and update in-degrees
for (int v : adj[u]) {
inDegree[v]--;
if (inDegree[v] == 0) {
queue.offer(v);
}
}
}
// Check for cycles
if (result.size() != n) {
return null; // Cycle detected
}
return result;
}vector<int> topologicalSort(vector<int> adj[], int n) {
vector<int> inDegree(n, 0);
// Calculate in-degrees
for (int v = 0; v < n; v++) {
for (int u : adj[v]) {
inDegree[u]++;
}
}
// Initialize queue with sources
queue<int> q;
for (int v = 0; v < n; v++) {
if (inDegree[v] == 0) {
q.push(v);
}
}
vector<int> result;
// Process sources iteratively
while (!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
// Remove u and update in-degrees
for (int v : adj[u]) {
inDegree[v]--;
if (inDegree[v] == 0) {
q.push(v);
}
}
}
// Check for cycles
if (result.size() != n) {
return {}; // Empty vector indicates cycle
}
return result;
}from collections import deque
def topological_sort(adj, n):
in_degree = [0] * n
# Calculate in-degrees
for v in range(n):
for u in adj[v]:
in_degree[u] += 1
# Initialize queue with sources
queue = deque()
for v in range(n):
if in_degree[v] == 0:
queue.append(v)
result = []
# Process sources iteratively
while queue:
u = queue.popleft()
result.append(u)
# Remove u and update in-degrees
for v in adj[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
# Check for cycles
if len(result) != n:
return None # Cycle detected
return resultTime Complexity: The time complexity is \(O(V + E)\), optimal for topological sorting:
Space Complexity: Auxiliary space is \(O(V)\):
This matches the optimal complexity for topological sorting, as we must examine every vertex and edge.