Hvad er topologisk sortering?

Question

Accepted Answer

**Topologisk sortering** ordner linjært hjørnerne i en **DAG** (rettet acyklisk graf) sådan at hver kant u->v har u **før** v. Det besvarer spørgsmålet "i hvilken rækkefølge kan jeg udføre disse opgaver givet deres afhængigheder?"

## Ideen

To almindelige tilgange: **Kahns algoritme** (fjern gentagne gange noder med indgangstrin 0) eller **DFS** (omvendt post-orden). En gyldig ordning eksisterer **kun hvis der ikke er en cyklus**.

## Eksempel (Kahns algoritme)

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

## Kompleksitet

- **Tid:** O(V + E). **Plads:** O(V).

## Hvornår skal det bruges / faldgruber

Brug til **build-systemer**, opgaveplanlægning, kursusforudsætninger og afhængighedsløsning. Hvis resultatet er kortere end V, har grafen en **cyklus** (ingen gyldig rækkefølge). Ordningen er generelt **ikke unik**.

## Hvorfor det betyder noget

Affængighedsordning er allestedsnærværende — compilere, pakkeadministratorer, regnearkgenberegning, CI-pipeline'r.

Topologisk sortering fungerer også som cyklusdetektion for rettede grafer.

At genkende et problem som "orden under betingelser" og gribe til topologisk sortering er et stærkt seniorsignal.