# Topological Sort — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/topological-sort

> DAG के nodes का रैखिक क्रम ताकि हर edge आगे की ओर इंगित करे — build systems और course scheduling की नींव।

## केवल 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 मौजूद है।

```python
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 मिलता है।

```python
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 तक सिमट जाते हैं।