Remove prerequisites before scheduling dependents
A topological order places every directed edge's source before its destination. Such an order exists exactly when the graph is acyclic. Kahn's algorithm repeatedly removes zero-indegree vertices.
fun topologicalOrder(graph: List<List<Int>>): List<Int>? {
require(graph.all { edges -> edges.all { it in graph.indices } })
val indegree = IntArray(graph.size)
graph.forEach { edges -> edges.forEach { indegree[it]++ } }
val queue = ArrayDeque<Int>()
indegree.indices.filterTo(queue) { indegree[it] == 0 }
val order = mutableListOf<Int>()
while (queue.isNotEmpty()) {
val node = queue.removeFirst()
order.add(node)
for (next in graph[node]) if (--indegree[next] == 0) queue.addLast(next)
}
return order.takeIf { it.size == graph.size }
}
A partial result means some cycle prevented completion; returning it as a valid complete order would hide a dependency error. Multiple valid orders may exist.
Exercise
Test a chain, independent vertices, a diamond, and a directed cycle. Verify every edge using a position map rather than expecting one arbitrary order.
Check: if lexicographically smallest order is required, use a priority queue for available vertices and account for the extra cost.