Vad är topologisk sortering?

Question

Accepted Answer

**Topologisk sortering** ordnar linjärt hörnen i en **DAG** (riktad acyklisk graf) så att varje kant u->v har u **före** v. Det svarar på frågan "i vilken ordning kan jag göra dessa uppgifter givet deras beroenden?"

## Idén

Två vanliga metoder: **Kahns algoritm** (ta bort noder med in-degree 0 upprepat) eller **DFS** (omvänd post-ordning). En giltig ordning existerar **endast om det inte finns någon cykel**.

## Exempel (Kahns algoritm)

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

## Komplexitet

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

## När du använder / fallgropar

Använd för **byggsystem**, schemaläggning av uppgifter, kursförutsättningar och beroendeytor. Om resultatet är kortare än V har grafen en **cykel** (ingen giltig ordning). Ordningen är i allmänhet **inte unik**.

## Varför det spelar roll

Beroendsortering finns överallt — kompilatorer, pakethanterare, omräkning av kalkylark, CI-pipelines.

Topologisk sortering fungerar också som cykeldetektering för riktade grafer.

Att känna igen ett problem som "ordning under begränsningar" och gripa till topologisk sortering är en stark signal för en senior-utvecklare.