Khóa học Python từ Cơ bản đến Nâng cao

Bài 13.3 - Topological Sort với Python

Topological Sort (Sắp xếp topo) là kỹ thuật sắp xếp các đỉnh của một đồ thị có hướng không chu trình (DAG) sao cho nếu có cạnh từ đỉnh u đến đỉnh v, thì u sẽ đứng trước v trong thứ tự sắp xếp.

Khi nào cần Topological Sort?

• Lập kế hoạch thực hiện các tác vụ có phụ thuộc
• Build hệ thống (task A phải xong trước task B)
• Compiling code, phân tích dependency giữa các module

Đồ thị ví dụ

graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['H', 'F'],
    'F': ['G'],
    'G': [],
    'H': []
}

Ví dụ: để chạy F, ta cần hoàn thành C, D, và E trước.

Cách 1: Cài đặt bằng DFS (Đệ quy)

def topo_sort_dfs(graph):
    visited = set()
    result = []

    def dfs(node):
        if node in visited:
            return
        visited.add(node)
        for neighbor in graph.get(node, []):
            dfs(neighbor)
        result.append(node)

    for node in graph:
        if node not in visited:
            dfs(node)

    result.reverse()
    return result

Ví dụ 1: Kết quả chạy DFS

order = topo_sort_dfs(graph)
print("Thứ tự topo (DFS):", order)

Kết quả mẫu:

Thứ tự topo (DFS): ['B', 'D', 'A', 'C', 'E', 'H', 'F', 'G']

Thứ tự có thể khác nhau tùy cách duyệt, miễn là đảm bảo điều kiện u → v thì u đứng trước v.

Cách 2: Kahn’s Algorithm (Duyệt theo in-degree)

from collections import deque

def topo_sort_kahn(graph):
    in_degree = {node: 0 for node in graph}

    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    queue = deque([node for node in graph if in_degree[node] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != len(graph):
        raise ValueError("Đồ thị có chu trình!")

    return result

Ví dụ 2: Kết quả chạy Kahn

order = topo_sort_kahn(graph)
print("Thứ tự topo (Kahn):", order)

Kết quả mẫu:

Thứ tự topo (Kahn): ['A', 'B', 'C', 'D', 'E', 'H', 'F', 'G']

So sánh 2 cách làm

Phân tích độ phức tạp

• V: số đỉnh
• E: số cạnh

Lưu ý quan trọng

• Chỉ áp dụng cho DAG – đồ thị không có chu trình
• Nếu tồn tại chu trình → Topological Sort không tồn tại

Gợi ý bài tập

1. Viết chương trình kiểm tra một đồ thị có phải DAG không
2. Ứng dụng sắp xếp topo trong hệ thống quản lý môn học có tiên quyết
3. Tìm tất cả các thứ tự topo hợp lệ (backtracking)

Tổng kết

• Topological Sort là công cụ cực mạnh khi xử lý bài toán có phụ thuộc thứ tự
• Có thể cài bằng DFS hoặc Kahn’s Algorithm tùy vào mục đích sử dụng
• Là nền tảng để học các thuật toán nâng cao hơn như Critical Path, Build Dependency,...