Topological Sort

Topological Sort is used to order vertices in a Directed Acyclic Graph (DAG) such that for every edge a→b, vertex a comes before vertex b. In DFS-based Topological Sort, the algorithm visits each vertex and explores its neighbors recursively. When an edge from a→b is encountered, it indicates that b depends on a, so a must come before b in the final ordering. After visiting all neighbors of a vertex, the vertex is pushed onto a stack. Once all vertices are processed, reversing the stack gives the correct topological order. This algorithm works only on DAGs, as cycles prevent a valid ordering.

TopologicalSort(graph):
    visited = empty set
    stack = empty stack

    for each node in graph:
        if node not in visited:
            DFS(graph, node, visited, stack)

    return stack (reversed)

DFS(graph, node, visited, stack):
    visited[node] = true

    for each neighbor in graph[node]:
        if neighbor not in visited:
            DFS(graph, neighbor, visited, stack)

    stack.push(node)