Kahn's Algorithm (Topological Sort)
BFS-based topological sort algorithm that removes vertices with in-degree 0 iteratively. Named after Arthur Kahn, it's an alternative to DFS-based topological sorting that can detect cycles efficiently. The algorithm maintains a queue of vertices with no incoming edges and processes them level by level.
Visualization
Interactive visualization for Kahn's Algorithm (Topological Sort)
Kahn's Algorithm (BFS Topological Sort)
• Time: O(V + E)
• BFS-based approach
• Detects cycles (result length < V)
Interactive visualization with step-by-step execution
Implementation
1function kahnsAlgorithm(graph: Map<number, number[]>, V: number): number[] {
2 const inDegree = new Array(V).fill(0);
3
4 for (const neighbors of graph.values()) {
5 for (const n of neighbors) {
6 inDegree[n]++;
7 }
8 }
9
10 const queue: number[] = [];
11 for (let i = 0; i < V; i++) {
12 if (inDegree[i] === 0) queue.push(i);
13 }
14
15 const result: number[] = [];
16
17 while (queue.length > 0) {
18 const node = queue.shift()!;
19 result.push(node);
20
21 for (const neighbor of graph.get(node) || []) {
22 inDegree[neighbor]--;
23 if (inDegree[neighbor] === 0) {
24 queue.push(neighbor);
25 }
26 }
27 }
28
29 return result.length === V ? result : [];
30}Deep Dive
Theoretical Foundation
Kahn's algorithm works by maintaining the in-degree (number of incoming edges) for each vertex. It repeatedly removes vertices with in-degree 0, which are safe to process since they have no dependencies. When a vertex is removed, the in-degrees of its neighbors are decremented. If all vertices are processed, the graph is acyclic and we have a valid topological ordering. If some vertices remain unprocessed, the graph contains a cycle. Time: O(V+E) to compute in-degrees and process all vertices/edges once.
Complexity
Time
O(V+E)
O(V+E)
O(V+E)
Space
O(V)
Applications
Industry Use
Build systems with dependency resolution
Course prerequisite scheduling
Package manager dependency resolution
Task scheduling in project management
Compiler optimization (instruction scheduling)
Deadlock detection in operating systems
Use Cases
Related Algorithms
Depth-First Search (DFS)
Graph traversal exploring as deep as possible before backtracking. DFS is a fundamental algorithm that uses a stack (either implicitly through recursion or explicitly) to explore graph vertices. It's essential for cycle detection, topological sorting, and pathfinding problems.
Breadth-First Search (BFS)
Level-by-level graph traversal guaranteeing shortest paths in unweighted graphs. BFS uses a queue to explore vertices level by level, making it optimal for finding shortest paths and solving problems that require exploring nearest neighbors first.
Dijkstra's Algorithm
Finds shortest path from source to all vertices in weighted graph with non-negative edges. Uses greedy approach with priority queue.
Floyd-Warshall Algorithm
Floyd-Warshall is an all-pairs shortest path algorithm that finds shortest distances between every pair of vertices in a weighted graph. Unlike Dijkstra (single-source), it computes shortest paths from all vertices to all other vertices simultaneously. The algorithm can handle negative edge weights but not negative cycles. Developed independently by Robert Floyd, Bernard Roy, and Stephen Warshall in the early 1960s.