Topological Sorting

Topological Sorting is an ordering of nodes in a directed acyclic graph (DAG) where each node appears before all the nodes it points to. It is like creating a list of tasks, ensuring that each task comes after any tasks it depends on. The sorting can be achieved using Kahn's algorithm or DFS with a stack. Kahn's algorithm works by repeatedly removing nodes with no incoming edges (zero in-degree) and adding them to the order.

Pseudocode

indeg = indegree()

stack = new Stack()

for each vertex v:

    if indeg[v] == 0: stack.push(v)

while stack is not empty:

    u = stack.pop()

    add u to sorted list

    for each neighbor v of u:

        indeg[v] = indeg[v] - 1

        if indeg[v] == 0: stack.push(v)

function indegree():

    indeg = map vertex -> 0

    for each vertex u:

        for each neighbor v of u:

            indeg[v] = indeg[v] + 1

    return indeg