Topological Sorting of Directed Acyclic Graphs (DAGs)

Topological sorting is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, vertex u comes before v in the ordering.

Key Concepts

Approaches to Topological Sorting

1. DFS Based Topological Sort

Use depth-first search to recursively visit nodes and add them to the ordering after exploring their adjacent vertices.

def topological_sort_dfs(graph):
    visited = set()
    stack = []

    def dfs(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)

    for vertex in graph:
        if vertex not in visited:
            dfs(vertex)
    stack.reverse()
    return stack

# Usage Example
graph = {
    5: [2, 0],
    4: [0, 1],
    2: [3],
    3: [1],
    0: [],
    1: []
}

print(topological_sort_dfs(graph))

2. BFS (Kahn’s Algorithm) Based Topological Sort

Maintain the indegree of all vertices and repeatedly remove vertices with indegree 0, thereby building the ordering.

from collections import deque

def topological_sort_bfs(graph):
    indegree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1

    queue = deque([u for u in graph if indegree[u] == 0])
    topo_order = []

    while queue:
        u = queue.popleft()
        topo_order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    if len(topo_order) == len(graph):
        return topo_order
    else:
        raise ValueError("Graph has at least one cycle, topological sort not possible")

# Usage Example
print(topological_sort_bfs(graph))

Applications