Learn
Topological Sort (DFS-based)
Topological Sort using DFS builds the ordering by adding vertices after all their descendants are processed. You reverse the finishing order to get the topological order.
You detect cycles using vertex colors: white (unvisited), gray (in progress), black (finished). A gray vertex encountered during traversal indicates a cycle.
function dfsTopologicalSort(graph, n):
color = array of size n, initialized to WHITE
result = empty stack
for v from n - 1 down to 0:
if color[v] == WHITE:
if not dfs(graph, v, color, result):
return -1
return result reversed
function dfs(graph, u, color, result):
color[u] = GRAY
for each neighbor v of u in reverse order:
if color[v] == GRAY:
return false
if color[v] == WHITE:
if not dfs(graph, v, color, result):
return false
color[u] = BLACK
result.push(u)
return true
Cycle detection: If you encounter a gray vertex while exploring, you've found a back edge indicating a cycle.
Why reverse finishing order works: When you finish a vertex, all vertices reachable from it are already in the stack.
Applications: You use DFS-based topological sort for build systems, compiler instruction scheduling, and determining execution order in spreadsheets.
Time complexity: for traversing all vertices and edges.
Space complexity: for color array and recursion stack.