Topological Sort (DFS-based) Algorithm Tutorial

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: $O(V + E)$ for traversing all vertices and edges.

Space complexity: $O(V)$ for color array and recursion stack.