Što je topološko sortiranje?

Question

Accepted Answer

**Topološko sortiranje** linearno uređuje vrhove **DAG-a** (usmjerenog acikličnog grafa) tako da se svaki brid u->v ima u **prije** v. Odgovara na pitanje "u kojem redoslijedu mogu izvršiti te zadatke s obzirom na njihove ovisnosti?"

## Ideja

Dva česta pristupa: **Kahnov algoritam** (ponavljano uklanjanje čvorova s in-degree 0) ili **DFS** (obrnuti post-order). Valjani redoslijed postoji **samo ako nema ciklusa**.

## Primjer (Kahnov algoritam)

```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']
```

## Složenost

- **Vrijeme:** O(V + E). **Prostor:** O(V).

## Kada koristiti / zamke

Koristite za **build sustave**, planiranje zadataka, preduvjete kolegija i rješavanje ovisnosti. Ako je rezultat kraći od V, graf ima **ciklus** (nema valjane sekvence). Redoslijed je općenito **nije jedinstven**.

## Zašto je to važno

Naređivanje ovisnosti je sveprisutno — kompajlatori, upravitelji paketa, ponovno računanje tablice, CI cjevovodi.

Topološko sortiranje služi i kao otkrivanje ciklusa za usmjerene grafove.

Prepoznavanja problema kao "naređivanja pod ograničenjima" i primjena topološkog sortiranja jasan je pokazatelj seniority.