️ Khan's Algorithm
Kahn's Algorithm solves one problem: given a list of tasks that depend on each other, what order can you safely do them all?
The Problem It Solves
Some tasks can only start after other tasks are finished. For example:
- You must connect to the database before you can run a query.
- You must load a class before you can instantiate it.
- You must create a table before you can insert rows into it.
When you have many tasks with many dependencies, figuring out the right order by hand becomes difficult fast. Kahn's Algorithm does it for you. The result is called a topological sort.
Core Concept: In-Degree
Every task keeps a counter called its in-degree: the number of unfinished tasks that must complete before it can start.
- In-degree 0 — nothing is blocking this task. It can run right now.
- In-degree 1 or more — this task must wait.
Kahn's Algorithm repeatedly finds tasks with in-degree 0, adds them to a queue (a waiting line where items are processed in the order they arrive), and then decreases the in-degree of every task that was waiting on them. Repeat until everything is done.
Step-by-Step Walkthrough
Suppose you have four tasks with these rules:
A must finish before C
B must finish before C
C must finish before DDraw that as a graph (an arrow means "must come before"):
A ──┐
▼
C ──► D
▲
B ──┘Step 1 — Count in-degrees
Go through every arrow and count how many arrows point into each task:
Task In-degree Reason
A 0 Nothing points to A
B 0 Nothing points to B
C 2 A and B both point to C
D 1 C points to D
Queue: []
Done: []Step 2 — Queue up tasks with in-degree 0
A and B have in-degree 0, so they are ready immediately. Put them in the queue:
Task In-degree Reason
A 0 (ready — joins the queue)
B 0 (ready — joins the queue)
C 2
D 1
Queue: [A, B]
Done: []Step 3 — Process the queue
Take A from the front of the queue. A is done. C was waiting on A, so its in-degree drops by 1:
Task In-degree Reason
A ✓ done
B 0
C 1 (was 2, A is now done)
D 1
Queue: [B]
Done: [A]Take B from the front of the queue. B is done. C was also waiting on B, so its in-degree drops to 0 — it is now unblocked and joins the queue:
Task In-degree Reason
A ✓ done
B ✓ done
C 0 (was 1, B is now done — joins the queue)
D 1
Queue: [C]
Done: [A, B]Take C from the front of the queue. C is done. D was waiting on C, so its in-degree drops to 0 and it joins the queue:
Task In-degree Reason
A ✓ done
B ✓ done
C ✓ done
D 0 (was 1, C is now done — joins the queue)
Queue: [D]
Done: [A, B, C]Take D from the front of the queue. D is done. Nothing was waiting on D, so nothing changes. The queue is now empty:
Task In-degree Reason
A ✓ done
B ✓ done
C ✓ done
D ✓ done
Queue: []
Done: [A, B, C, D] ✓ finishedPHP Implementation
Here is a clean, self-contained PHP function that runs Kahn's Algorithm on any graph you give it:
<?php
/**
* Returns the nodes of $graph in topological order.
*
* $graph is an associative array where each key is a node
* and each value is an array of nodes that depend on it
* (i.e. must come *after* it).
*
* @param array<string, string[]> $graph
* @return string[]
* @throws \Exception if a circular dependency is detected
*/
function kahnTopologicalSort(array $graph): array {
// Step 1: Count in-degrees
// We use ??= 0 so nodes that are never a dependency still appear in the array.
$inDegree = [];
foreach ($graph as $node => $dependents) {
$inDegree[$node] ??= 0;
foreach ($dependents as $dependent) {
$inDegree[$dependent] ??= 0;
$inDegree[$dependent]++;
}
}
// Step 2: Queue up tasks with in-degree 0
$queue = [];
foreach ($inDegree as $node => $count) {
if ($count === 0) {
$queue[] = $node;
}
}
// Step 3: Process the queue
$result = [];
while (!empty($queue)) {
// Take the next ready node.
$node = array_shift($queue);
$result[] = $node;
// Unblock anything that was waiting on this node.
foreach ($graph[$node] as $dependent) {
$inDegree[$dependent]--;
if ($inDegree[$dependent] === 0) {
$queue[] = $dependent;
}
}
}
// Step 4: If not every node made it into $result, there is a cycle.
if (count($result) !== count($inDegree)) {
throw new \Exception('Circular dependency detected — no valid order exists.');
}
return $result;
}Example and output:
// The A → C ← B → D graph from the walkthrough above.
$graph = [
'A' => ['C'], // A must finish before C
'B' => ['C'], // B must finish before C
'C' => ['D'], // C must finish before D
'D' => [], // D has no dependents
];
print_r(kahnTopologicalSort($graph));
// Output
Array
(
[0] => A
[1] => B
[2] => C
[3] => D
)Note: A and B have no dependency between them, so the algorithm is free to place either one first. Both orderings are correct.
Detecting Circular Dependencies
Sometimes a set of dependencies is impossible to satisfy:
$circular = [
'A' => ['B'], // A must finish before B
'B' => ['C'], // B must finish before C
'C' => ['A'], // C must finish before A ← impossible!
];A waits for C, C waits for B, B waits for A — everyone is waiting and nobody can start. Kahn's Algorithm catches this automatically: if the queue empties before all nodes have been processed, at least one cycle exists. The function above throws an exception in that case rather than silently returning a wrong answer.
A Real-World Example: Class Autoloading
Imagine you are writing a dependency injection container. Some services depend on other services being instantiated first:
$graph = [
'Config' => ['Logger', 'Database'],
'Logger' => ['Database', 'AuthService'],
'Database' => ['UserRepo'],
'UserRepo' => ['AuthService'],
'AuthService' => [],
];
$bootOrder = kahnTopologicalSort($graph);
// Result: ['Config', 'Logger', 'Database', 'UserRepo', 'AuthService']
foreach ($bootOrder as $service) {
$container->boot($service);
}Every service is booted exactly once, in an order that guarantees its dependencies are already available.
Diagram
This diagram illustrates how the algorithm works.
Key Takeaways
- The in-degree of a node is the number of prerequisites still outstanding.
- Nodes with in-degree 0 are always safe to process next.
- After processing a node, decrease the in-degree of everything that depended on it.
- If the queue empties before all nodes are processed, a circular dependency exists.
- Time complexity is O(V + E) — linear in the number of nodes (V) and edges (E).