Apakah pengurutan topologi?

Question

Accepted Answer

**Topological sort** menyusun secara linear bucu-bucu **DAG** (directed acyclic graph) sehingga setiap tepi u->v memiliki u **sebelum** v. Ia menjawab "dalam urutan apakah saya dapat melakukan tugas-tugas ini mengingat kebergantungannya?"

## Ideanya

Dua pendekatan umum: **algoritma Kahn** (keluarkan berulang kali nod dengan in-degree 0) atau **DFS** (reverse post-order). Urutan yang sah wujud **hanya jika tidak ada kitaran**.

## Contoh (algoritma Kahn)

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

## Kerumitan

- **Masa:** O(V + E). **Ruang:** O(V).

## Bila hendak digunakan / jerat

Gunakan untuk **build systems**, penjadualan tugas, prasyarat kursus, dan penyelesaian kebergantungan. Jika hasilnya lebih pendek daripada V, graf mempunyai **kitaran** (tiada urutan sah). Urutannya pada amnya **bukan unik**.

## Mengapa ia penting

Pengurutan kebergantungan terdapat di mana-mana — pengkompil, pengurus pakej, pengiraan semula hamparan, saluran CI.

Topological sort juga berfungsi sebagai pengesanan kitaran untuk graf terarah.

Mengiktiraf masalah sebagai "pesanan di bawah kekangan" dan menggunakan topo sort adalah isyarat senior yang kuat.