ayodhyya.comTopological sorting orders vertices of a Directed Acyclic Graph (DAG) such that for every directed edge u→v, u appears before v. It is essential for scheduling, dependency resolution, and build systems.
Two primary methods—Kahn's algorithm (BFS-based) and DFS-based sorting—each offer different advantages for processing DAGs.
Kahn's Algorithm
Kahn's algorithm uses in-degree counting and a queue. Vertices with zero in-degree are processed first, and their outgoing edges are removed, reducing the in-degree of neighbors. This process repeats until all vertices are ordered.
Kahn's algorithm naturally detects cycles: if the output size is less than V, the graph contains a cycle and no topological order exists.
vector kahnsTopoSort(vector>& graph) {
int V = graph.size();
vector inDegree(V, 0), result;
for (int u = 0; u < V; u++)
for (int v : graph[u]) inDegree[v]++;
queue q;
for (int i = 0; i < V; i++)
if (inDegree[i] == 0) q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
result.push_back(u);
for (int v : graph[u])
if (--inDegree[v] == 0) q.push(v);
}
return result.size() == V ? result : vector();
} DFS-Based Topological Sort
DFS-based topological sort performs a depth-first traversal and appends vertices to a stack after processing all their dependencies. The stack is then popped to yield the topological order.
This method is intuitive and uses a visited set with recursion or an explicit stack. Cycle detection uses a recursion stack to track back edges.
bool dfs(int u, vector>& graph, vector& visited, vector& result) {
visited[u] = 1; // visiting
for (int v : graph[u]) {
if (visited[v] == 1) return false; // cycle
if (visited[v] == 0 && !dfs(v, graph, visited, result)) return false;
}
visited[u] = 2; // done
result.push_back(u);
return true;
}
vector topologicalSort(vector>& graph) {
int V = graph.size();
vector visited(V, 0), result;
for (int i = 0; i < V; i++)
if (visited[i] == 0 && !dfs(i, graph, visited, result)) return {};
reverse(result.begin(), result.end());
return result;
} Frequently Asked Questions
What makes a graph valid for topological sort?
The graph must be a Directed Acyclic Graph (DAG). Any directed cycle makes topological ordering impossible because of circular dependencies.
How does topological sort detect cycles?
Kahn's algorithm detects cycles when processed vertices count < total vertices. DFS detects cycles via back edges—when a vertex in the current recursion stack is revisited.
Originally published on Ayodhyya. Last updated June 1, 2026.