Topological Sort Algorithm

Topological Sort Order:

How Topological Sort Works

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. It's typically used for scheduling jobs or tasks with dependencies.

Color representation:

• Blue nodes are not yet visited
• Yellow node is the current node being explored
• Green nodes have been visited and are in the sorted order

function topologicalSort(graph):
    visited = set()
    stack = []

    for each vertex in graph:
        if vertex not in visited:
            dfsTopologicalSort(graph, vertex, visited, stack)

    return reversed(stack)

function dfsTopologicalSort(graph, vertex, visited, stack):
    visited.add(vertex)

    for each neighbor in graph.getNeighbors(vertex):
        if neighbor not in visited:
            dfsTopologicalSort(graph, neighbor, visited, stack)

    stack.append(vertex)
    visualize(visited, stack)

function visualize(visited, stack):
    // Update UI to show:
    // 1. Vertices that have been visited
    // 2. Current state of the stack
    // 3. Highlight the vertex currently being processed
    // 4. Show the partial ordering of vertices discovered so far