Kaj je topološko sortiranje?

Question

Accepted Answer

**Topološko sortiranje** linearno uredi vozlišča **DAG**-a (usmerjenega aciklličnega grafa) tako, da ima vsak rob u->v u **pred** v. Odgovori na vprašanje "v kakšnem vrstnem redu lahko opravim te naloge glede na njihove odvisnosti?"

## Ideja

Dva pogosta pristopa: **Kahnov algoritem** (ponavljajoče odstranjevanje vozlišč z vhodno stopnjo 0) ali **DFS** (obratni post-order). Veljaven vrstni red obstaja **le če ni cikla**.

## Primer (Kahnov algoritem)

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

## Časovna zahtevnost

- **Čas:** O(V + E). **Prostor:** O(V).

## Kdaj uporabiti / pasti

Uporabite za **sisteme gradnje**, razporejanje nalog, predpogoje predmetov in razreševanje odvisnosti. Če je rezultat krajši od V, ima graf **cikel** (ni veljavnega reda). Vrstni red na splošno **ni enoten**.

## Zakaj je to pomembno

Urejevanje odvisnosti je povsod — prevajalniki, upravljalniki paketov, ponovno izračunavanje preglednic, CI cevovodi.

Topološko sortiranje hkrati služi kot odkrivanje ciklov za usmerjena grafa.

Prepoznavanje problema kot "urejanja pod pogoji" in seganje po topološkem sortiranju je močan signal za starejšega programerja.