Topological Sort produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u→v, u appears before v. It is implemented with DFS (reverse finish order) or Kahn's BFS algorithm (process nodes with in-degree 0 first). Used for task scheduling and dependency resolution.
void dfsTopoSort(int v, vector<vector<int>>& adj, vector<bool>& visited, stack<int>& stk) {
visited[v]=true;
for(int u:adj[v]) if(!visited[u]) dfsTopoSort(u,adj,visited,stk);
stk.push(v);
}
vector<int> topoSort(int n, vector<vector<int>>& adj){
vector<bool> visited(n,false); stack<int> stk;
for(int i=0;i<n;i++) if(!visited[i]) dfsTopoSort(i,adj,visited,stk);
vector<int> order;
while(!stk.empty()){order.push_back(stk.top());stk.pop();}
return order;
}Topological sort only exists for Directed Acyclic Graphs. If the graph has a cycle, no valid ordering exists. The DFS-based algorithm implicitly detects cycles through back edges.
Run DFS on the graph. When all descendants of a node are processed (DFS finishes), push the node onto a stack. Popping the stack gives the topological order.
Alternatively: compute in-degrees of all nodes. Start a queue with all zero-in-degree nodes. Process each node and reduce in-degrees of its neighbors. Nodes reaching zero in-degree join the queue.
Topological sort is used for: build systems (make, Gradle), task scheduling with dependencies, course prerequisite ordering, and resolving symbol dependencies in linkers.
Quiz coming soon for this algorithm.