Topological sort là gì?

Question

IT Interview Practice · Accepted Answer

**Topological sort** sắp thứ tự tuyến tính các đỉnh của một **DAG** (đồ thị có hướng không chu trình) sao cho mọi cạnh u->v có u **đứng trước** v. Nó trả lời "tôi có thể thực hiện các tác vụ này theo thứ tự nào dựa trên các phụ thuộc của chúng?"

## Ý tưởng

Hai cách tiếp cận phổ biến: **thuật toán Kahn** (liên tục loại bỏ các nút có bậc vào bằng 0) hoặc **DFS** (hậu thứ tự đảo ngược - reverse post-order). Một thứ tự hợp lệ chỉ tồn tại **khi không có chu trình**.

## Ví dụ (thuật toán 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                 # đếm các cạnh đi vào
    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                 # "loại bỏ" cạnh
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == len(graph) else None  # None -> có chu trình

topo_sort({'shirt': ['tie'], 'tie': ['jacket'], 'jacket': []})
# -> ['shirt', 'tie', 'jacket']
```

## Độ phức tạp

- **Thời gian:** O(V + E). **Bộ nhớ:** O(V).

## Khi nào dùng / những cạm bẫy

Dùng cho **hệ thống build**, lập lịch tác vụ, môn học tiên quyết, và giải quyết phụ thuộc. Nếu kết quả ngắn hơn V, đồ thị có một **chu trình** (không có thứ tự hợp lệ). Thứ tự nói chung **không duy nhất**.

## Tại sao điều này quan trọng

Sắp xếp theo phụ thuộc có ở khắp nơi — trình biên dịch, trình quản lý gói, tính lại bảng tính, đường ống CI.

Topological sort còn kiêm luôn vai trò phát hiện chu trình cho đồ thị có hướng.

Nhận ra một bài toán là "sắp thứ tự dưới ràng buộc" và nghĩ đến topo sort là một tín hiệu senior mạnh mẽ.

Ý tưởng

Ví dụ (thuật toán Kahn)

Độ phức tạp

Khi nào dùng / những cạm bẫy

Tại sao điều này quan trọng

Câu hỏi liên quan