Kahn's Algorithm
Description
Kahn's algorithm is a method for performing a topological sort on a directed acyclic graph (DAG). It works by repeatedly removing vertices with no incoming edges and adding them to the result list. This process continues until all vertices are processed or a cycle is detected.
History
The algorithm was developed by Arthur B. Kahn in 1962 and was published in his paper "Topological sorting of large networks". At the time, Kahn was working at Mathematical Analysis Research Corporation. The algorithm was developed to solve the practical problem of scheduling tasks with dependencies, which naturally forms a directed acyclic graph. The algorithm's simplicity and efficiency made it a fundamental tool in computer science, particularly in build systems, dependency resolution, and task scheduling.
How It Works
- Calculate in-degree for all vertices
- Add all vertices with in-degree 0 to a queue
- While queue is not empty:
- Remove a vertex from queue
- Add it to result list
- Reduce in-degree of all adjacent vertices by 1
- If any vertex's in-degree becomes 0, add it to queue
- If all vertices are visited, return result
- If not all vertices are visited, graph has a cycle
Visualization
Click Start to begin
Implementation
from collections import defaultdict, deque
class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.V = vertices
def add_edge(self, u, v):
self.graph[u].append(v)
def topological_sort(self):
# Calculate in-degree for all vertices
in_degree = [0] * self.V
for i in self.graph:
for j in self.graph[i]:
in_degree[j] += 1
# Create queue and add all vertices with in-degree 0
queue = deque()
for i in range(self.V):
if in_degree[i] == 0:
queue.append(i)
result = []
count = 0
# Process vertices
while queue:
# Remove vertex from queue
u = queue.popleft()
result.append(u)
count += 1
# Reduce in-degree for all adjacent vertices
for i in self.graph[u]:
in_degree[i] -= 1
# If in-degree becomes 0, add to queue
if in_degree[i] == 0:
queue.append(i)
# Check if graph has a cycle
if count != self.V:
return None # Graph has a cycle
return result
# Example usage
if __name__ == "__main__":
g = Graph(6)
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)
result = g.topological_sort()
if result is None:
print("Graph contains a cycle")
else:
print("Topological Sort:", " → ".join(map(str, result)))
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
int V;
vector<vector<int>> adj;
public:
Graph(int vertices) : V(vertices) {
adj.resize(V);
}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
vector<int> topologicalSort() {
vector<int> inDegree(V, 0);
// Calculate in-degree
for(int u = 0; u < V; u++) {
for(int v : adj[u]) {
inDegree[v]++;
}
}
// Add vertices with in-degree 0 to queue
queue<int> q;
for(int i = 0; i < V; i++) {
if(inDegree[i] == 0) {
q.push(i);
}
}
vector<int> result;
int count = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
count++;
// Reduce in-degree of adjacent vertices
for(int v : adj[u]) {
inDegree[v]--;
if(inDegree[v] == 0) {
q.push(v);
}
}
}
// Check if graph has cycle
if(count != V) {
return vector<int>(); // Return empty vector if cycle exists
}
return result;
}
};
int main() {
Graph g(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
vector<int> result = g.topologicalSort();
if(result.empty()) {
cout << "Graph contains a cycle" << endl;
} else {
cout << "Topological Sort: ";
for(int i = 0; i < result.size(); i++) {
cout << result[i];
if(i < result.size() - 1) cout << " → ";
}
cout << endl;
}
return 0;
}
public class Graph
{
private int V;
private List<List<int>> adj;
public Graph(int vertices)
{
V = vertices;
adj = new List<List<int>>();
for (int i = 0; i < V; i++)
{
adj.Add(new List<int>());
}
}
public void AddEdge(int u, int v)
{
adj[u].Add(v);
}
public List<int> TopologicalSort()
{
// Calculate in-degree for all vertices
int[] inDegree = new int[V];
foreach (var neighbors in adj)
{
foreach (var v in neighbors)
{
inDegree[v]++;
}
}
// Create queue and add all vertices with in-degree 0
Queue<int> queue = new Queue<int>();
for (int i = 0; i < V; i++)
{
if (inDegree[i] == 0)
{
queue.Enqueue(i);
}
}
List<int> result = new List<int>();
int count = 0;
// Process vertices
while (queue.Count > 0)
{
int u = queue.Dequeue();
result.Add(u);
count++;
// Reduce in-degree for all adjacent vertices
foreach (int v in adj[u])
{
inDegree[v]--;
if (inDegree[v] == 0)
{
queue.Enqueue(v);
}
}
}
// Check if graph has a cycle
if (count != V)
{
return null; // Graph has a cycle
}
return result;
}
}
public class Program
{
public static void Main()
{
Graph g = new Graph(6);
g.AddEdge(5, 2);
g.AddEdge(5, 0);
g.AddEdge(4, 0);
g.AddEdge(4, 1);
g.AddEdge(2, 3);
g.AddEdge(3, 1);
var result = g.TopologicalSort();
if (result == null)
{
Console.WriteLine("Graph contains a cycle");
}
else
{
Console.WriteLine("Topological Sort: " +
string.Join(" → ", result));
}
}
}
Complexity Analysis
Time Complexity
The time complexity of Kahn's algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This can be broken down into:
-
Calculating in-degrees: O(V + E)
- Iterating through all vertices: O(V)
- Processing each edge once: O(E)
-
Processing vertices: O(V + E)
- Each vertex enters queue once: O(V)
- Each edge is processed once: O(E)
Space Complexity
The space complexity is O(V), which includes:
-
In-degree array: O(V)
- Stores in-degree count for each vertex
-
Queue: O(V)
- Can contain at most V vertices
-
Result array: O(V)
- Stores the topological ordering
Advantages and Disadvantages
Advantages
- Simple and intuitive implementation
- Linear time complexity O(V + E)
- Can detect cycles in the graph
- Useful for dependency resolution
Disadvantages
- Only works with directed acyclic graphs
- Requires additional space for in-degree tracking
- May not preserve all valid orderings
- Not suitable for dynamic graphs