Co to jest sortowanie topologiczne?

Question

Accepted Answer

**Topological sort** porządkuje liniowo wierzchołki **DAG** (directed acyclic graph) tak, aby dla każdej krawędzi u->v wierzchołek u był **przed** v. Odpowiada na pytanie "w jakiej kolejności mogę wykonać te zadania biorąc pod uwagę ich zależności?"

## Idea

Dwa popularne podejścia: **algorytm Kahna** (wielokrotnie usuwaj węzły ze stopniem wejściowym 0) lub **DFS** (reverse post-order). Prawidłowe porządkowanie istnieje **tylko jeśli nie ma cyklu**.

## Przykład (algorytm Kahna)

```python
from collections import deque

def topo_sort(graph):
    indeg = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1                 # count incoming edges
    queue = deque([u for u in indeg if indeg[u] == 0])
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1                 # "remove" the edge
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == len(graph) else None  # None -> cycle

topo_sort({'shirt': ['tie'], 'tie': ['jacket'], 'jacket': []})
# -> ['shirt', 'tie', 'jacket']
```

## Złożoność

- **Czas:** O(V + E). **Przestrzeń:** O(V).

## Kiedy używać / pułapki

Używaj do **systemów budowania**, planowania zadań, wymagań wstępnych do kursów i rozwiązywania zależności. Jeśli wynik jest krótszy niż V, graf ma **cykl** (brak prawidłowego porządku). Porządkowanie generalnie **nie jest unikalne**.

## Dlaczego to ważne

Porządkowanie zależności jest wszędzie — kompilatory, menedżery pakietów, przeliczanie arkuszy kalkulacyjnych, potoki CI.

Sortowanie topologiczne pełni również rolę detekcji cyklu dla grafów skierowanych.

Rozpoznanie problemu jako "porządkowanie pod ograniczeniami" i sięgnięcie po sortowanie topologiczne to mocny sygnał seniora.