Sắp xếp tô-pô (topological sort) là gì: cách hoạt động, code và độ phức tạp

Sắp xếp tô-pô giải bài toán gì

Nhiều công việc thực tế có điều kiện tiên quyết: một môn học yêu cầu các môn trước, một tệp nguồn phải được biên dịch sau các tệp mà nó import, một gói phải được cài sau các phụ thuộc của nó, một ô bảng tính phải được tính sau các ô mà nó tham chiếu. Hãy vẽ mỗi công việc là một nút và mỗi quy tắc “phải làm trước” là một cạnh có hướng. Thứ tự tô-pô là bất kỳ dãy công việc nào thỏa mọi cạnh.

Thứ tự tồn tại khi và chỉ khi đồ thị không có chu trình có hướng. Nếu A cần B và B cần A thì không có thứ tự hợp lệ, và một phép sắp xếp tô-pô tốt sẽ báo điều đó thay vì lặp mãi. Một DAG thường có nhiều thứ tự hợp lệ; các thuật toán chỉ trả về một trong số đó.

Ý tưởng bằng lời đơn giản

Thuật toán Kahn (do Arthur Kahn công bố năm 1962) làm việc từ phía trước:

1. Đếm số cạnh đi vào (bậc vào, in-degree) của mọi nút.
2. Đưa mọi nút có bậc vào bằng 0 vào hàng đợi: các việc này không còn điều kiện tiên quyết nào chưa thỏa.
3. Lấy một nút từ hàng đợi và thêm vào kết quả. Với mỗi cạnh đi ra của nó, giảm bậc vào của nút đích đi 1; nếu về 0 thì thêm nút đích vào hàng đợi.
4. Khi hàng đợi rỗng, nếu kết quả chứa mọi nút thì đó là một thứ tự tô-pô. Nếu không, các nút còn lại thuộc một chu trình.

Phương pháp DFS làm việc từ phía sau: một nút chỉ hoàn tất sau khi mọi nút nó trỏ tới đã hoàn tất, nên liệt kê các nút theo thứ tự hoàn tất ngược sẽ đặt mỗi nút trước mọi nút kế tiếp của nó.

Ví dụ từng bước

Mặc quần áo: underwear → pants, pants → shoes, socks → shoes, pants → belt, shirt → belt, shirt → tie, tie → jacket, belt → jacket. Thuật toán Kahn, lấy các nút trong hàng đợi theo thứ tự vào trước ra trước:

Thứ tự cuối cùng: underwear, socks, shirt, pants, tie, shoes, belt, jacket. Cả 8 nút đều được xếp, nên không có chu trình.

Cài đặt bằng Python

Thuật toán Kahn với deque:

from collections import deque
def topo_sort(graph):
    """graph: dict node -> list of nodes that must come after it."""
    indegree = {n: 0 for n in graph}
    for n in graph:
        for m in graph[n]:
            indegree[m] += 1
    queue = deque(n for n in graph if indegree[n] == 0)
    order = []
    while queue:
        n = queue.popleft()
        order.append(n)
        for m in graph[n]:
            indegree[m] -= 1
            if indegree[m] == 0:
                queue.append(m)
    if len(order) != len(graph):
        raise ValueError("graph has a cycle")
    return order
dress = {
    "underwear": ["pants"], "socks": ["shoes"], "shirt": ["belt", "tie"],
    "pants": ["shoes", "belt"], "tie": ["jacket"], "belt": ["jacket"],
    "shoes": [], "jacket": [],
}
print(topo_sort(dress))
# ['underwear', 'socks', 'shirt', 'pants', 'tie', 'shoes', 'belt', 'jacket']

Phiên bản DFS thêm một nút vào sau khi mọi nút kế tiếp của nó đã xong, rồi đảo ngược danh sách:

def topo_sort_dfs(graph):
    order, state = [], {}             # state: 1 = in progress, 2 = done
    def visit(n):
        if state.get(n) == 1:
            raise ValueError("graph has a cycle")
        if state.get(n) == 2:
            return
        state[n] = 1
        for m in graph[n]:
            visit(m)
        state[n] = 2
        order.append(n)
    for n in graph:
        visit(n)
    return order[::-1]
print(topo_sort_dfs(dress))
# ['shirt', 'tie', 'socks', 'underwear', 'pants', 'belt', 'jacket', 'shoes']

Cả hai kết quả đều hợp lệ. Từ Python 3.9, thư viện chuẩn cũng có graphlib.TopologicalSorter. Lưu ý nó nhận ánh xạ từ mỗi nút tới các nút đứng trước nó, ngược chiều với các dictionary ở trên:

from graphlib import TopologicalSorter
ts = TopologicalSorter({"b": {"a"}, "c": {"a", "b"}})   # node: its prerequisites
print(list(ts.static_order()))  # ['a', 'b', 'c']

Độ phức tạp thời gian và không gian

Biến thể và lỗi thường gặp

• Thứ tự nhỏ nhất trước: thay hàng đợi bằng min-heap (heapq) để luôn chọn nút nhỏ nhất đang khả dụng. Cách này cho thứ tự nhỏ nhất theo từ điển trong O((V + E) log V).
• Lập lịch song song: chạy thuật toán Kahn theo từng vòng, lấy cùng lúc mọi nút có bậc vào 0. Mỗi vòng là một lô công việc có thể chạy đồng thời; số vòng bằng độ dài chuỗi phụ thuộc dài nhất. graphlib.TopologicalSorter hỗ trợ việc này qua get_ready() và done().
• Đường đi dài nhất hoặc ngắn nhất trong DAG: nới lỏng các cạnh theo thứ tự tô-pô để có kết quả trong O(V + E), kể cả với trọng số âm.
• Đếm số thứ tự khác nhau là bài toán khó hơn nhiều; đừng cố liệt kê hết chúng với đồ thị lớn.

Phiên bản DFS đệ quy gặp cùng vấn đề giới hạn đệ quy như mọi DFS đệ quy trong Python: với chuỗi hàng nghìn nút, hãy dùng thuật toán Kahn.

Khi nào dùng và ứng dụng thực tế

• Công cụ build như Make sắp xếp các target theo phụ thuộc, và trình quản lý gói sắp xếp thứ tự cài đặt theo đồ thị phụ thuộc.
• Bảng tính tính lại các ô theo thứ tự phụ thuộc và báo tham chiếu vòng.
• Bộ lập lịch tác vụ và công cụ workflow, ví dụ các pipeline dữ liệu dạng DAG, chạy tác vụ theo thứ tự tô-pô.
• Trình biên dịch sắp xếp các khai báo và đánh giá đồ thị biểu thức; cơ sở dữ liệu sắp xếp thứ tự tạo hoặc xóa khóa ngoại.
• Bài phỏng vấn: course schedule I và II, alien dictionary (thứ tự chữ cái từ các từ đã sắp xếp), parallel courses, chiều cao tối thiểu của một kế hoạch build.