Learn
Topological Sort (Kahn's Algorithm)
Topological Sort arranges vertices of a directed acyclic graph (DAG) so every edge goes from earlier to later in the ordering. Kahn's Algorithm uses BFS, repeatedly removing vertices with no incoming edges.
A topological ordering only exists for DAGs. If the graph has a cycle, no valid ordering exists.
function kahnTopologicalSort(graph, n):
inDegree = array of size n, initialized to 0
for each edge (u, v):
inDegree[v] = inDegree[v] + 1
queue = min-priority queue
for v from 0 to n - 1:
if inDegree[v] == 0:
queue.push(v)
result = empty list
while queue is not empty:
u = queue.pop()
result.append(u)
for each neighbor v of u:
inDegree[v] = inDegree[v] - 1
if inDegree[v] == 0:
queue.push(v)
if length of result != n:
return -1
return result
Cycle detection: If your result has fewer than vertices, the graph has a cycle.
Lexicographically smallest: Use a min-priority queue to always pick the smallest available vertex.
Applications: You use topological sort for build systems (Make, Gradle), course prerequisites, task scheduling, and dependency resolution.
Time complexity: for the algorithm, with priority queue.