Apa iku topological sorting?

Question

IT Interview Practice · Accepted Answer

**Topological sort** ngaturake verteks saka **DAG** (directed acyclic graph) kanthi linear, supaya saben edge u->v duwe u **sadurunge** v. Iki nduweni jawaban "saben sapa bisa nggawa tugas-tugas iki gegayutan karo dependensine?"

## Ideya

Rong cara umum: **algoritma Kahn** (bola-bali busak node kanthi in-degree 0) utawa **DFS** (reverse post-order). Urutan sing sah ana **mung yen ora ana sikol**.

## Conto (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']
```

## Kompleksitas

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

## Kapan migunake / keselanan

Gunakake kanggo **build system**, task scheduling, prasyarat kursus, lan dependency resolution. Yen asile luwih cekak tinimbang V, grafik duwe **sikol** (ora ana urutan sing sah). Urutan umume **ora unik**.

## Mengapa penting

Pemerintahan dependensi ana ing mana-mana — compiler, package manager, pangitung ulang spreadsheet, pipeline CI.

Topological sort bisa digunakake minangka cycle detection kanggo directed graph.

Akeh ngenali masalah minangka "order under constraints" lan nggunakake topo sort minangka signal senior sing kuwat.

Ideya

Conto (algoritma Kahn)

Kompleksitas

Kapan migunake / keselanan

Mengapa penting

Pitakon sing gegandhengan