Topological Sort

केवल DAG पर काम करता है

Topological sort, एक Directed Acyclic Graph (DAG) के nodes को ऐसे क्रम में रखता है कि हर edge u -> v के लिए u, v से पहले आए। यह केवल तब मौजूद होता है जब graph में कोई cycle न हो — जैसे task scheduling जहाँ कुछ tasks दूसरों पर निर्भर हों।

Kahn's algorithm (BFS)

बार-बार वे nodes हटाएँ जिनकी in-degree 0 है, और उनके पड़ोसियों की in-degree घटाएँ। अगर n से कम nodes हटें, तो cycle मौजूद है।

from collections import deque

def topo_sort(n, edges):
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        g[u].append(v)
        indeg[v] += 1

    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    return order if len(order) == n else []  # [] means a cycle exists

DFS variant

DFS चलाएँ और हर node को उसके सभी descendants देखने के बाद stack में डालें (post-order)। उस stack को उल्टा करने पर सही topological order मिलता है।

def topo_dfs(n, g):
    visited = [False] * n
    stack = []

    def dfs(u):
        visited[u] = True
        for v in g[u]:
            if not visited[v]:
                dfs(v)
        stack.append(u)

    for u in range(n):
        if not visited[u]:
            dfs(u)
    return stack[::-1]

कहाँ दिखता है

Build systems (compile क्रम), course prerequisites, dependencies resolve करने वाले package managers, और dependency graph में cycle पहचानना — सब topological sort तक सिमट जाते हैं।