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

Bài 13.4 - Python: giải bài dependency

Trong lập trình và thực tế, nhiều khi chúng ta gặp phải bài toán:

Có một loạt tác vụ, mỗi tác vụ có thể phụ thuộc vào một số tác vụ khác. Làm sao sắp xếp chúng để không vi phạm sự phụ thuộc?

Đây chính là bài toán dependency resolution – và bạn hoàn toàn có thể giải bằng Topological Sort trong đồ thị có hướng.

Ví dụ đề bài

tasks = {
    'Build PC': ['Install Windows'],
    'Install Windows': ['Assemble Hardware'],
    'Install Software': ['Install Windows'],
    'Assemble Hardware': []
}

Mục tiêu:

Tìm thứ tự thực hiện các tác vụ sao cho mỗi tác vụ chỉ thực hiện khi các tác vụ phụ thuộc đã hoàn thành.

Cài đặt giải bằng Topological Sort (DFS)

def resolve_dependencies(tasks):
    visited = set()
    result = []

    def dfs(task):
        if task in visited:
            return
        visited.add(task)
        for dependency in tasks.get(task, []):
            dfs(dependency)
        result.append(task)

    for task in tasks:
        if task not in visited:
            dfs(task)

    result.reverse()
    return result

Chạy ví dụ

order = resolve_dependencies(tasks)
print("Thứ tự thực hiện:", order)

Kết quả:

Thứ tự thực hiện: ['Assemble Hardware', 'Install Windows', 'Build PC', 'Install Software']

Tất cả phụ thuộc được đảm bảo đúng thứ tự: trước khi "Install Windows" thì phải "Assemble Hardware", v.v.

Giải thích chi tiết

• Ta dùng DFS để duyệt các dependency trước.
• Mỗi task sau khi đã duyệt hết phụ thuộc sẽ được thêm vào result.
• result.reverse() để đưa task phụ thuộc lên trước.

Phát hiện chu trình

Trong bài toán thật, có thể có vòng lặp (circular dependency). Để kiểm tra, ta thêm visiting:

def resolve_dependencies_with_check(tasks):
    visited = set()
    visiting = set()
    result = []

    def dfs(task):
        if task in visiting:
            raise ValueError(f"Chu trình phát hiện tại: {task}")
        if task in visited:
            return
        visiting.add(task)
        for dependency in tasks.get(task, []):
            dfs(dependency)
        visiting.remove(task)
        visited.add(task)
        result.append(task)

    for task in tasks:
        dfs(task)

    result.reverse()
    return result

Ví dụ với vòng lặp

tasks = {
    'A': ['B'],
    'B': ['C'],
    'C': ['A']
}

resolve_dependencies_with_check(tasks)

Kết quả:

ValueError: Chu trình phát hiện tại: A

Topological Sort không thể thực hiện nếu đồ thị có chu trình!

Ứng dụng thực tế

• Build hệ thống: Module A cần module B và C
• Cài đặt package: apt, npm, pip phải xử lý dependency
• Game logic: event/phép thuật xảy ra theo chuỗi

Độ phức tạp

• V: số lượng task
• E: tổng số dependency

Tổng kết

• Bài toán dependency là ứng dụng thực tế điển hình của Topological Sort
• Cài đặt đơn giản, dễ mở rộng, dễ tích hợp vào các hệ thống lớn
• Hãy luôn kiểm tra chu trình để tránh lỗi logic hoặc vòng lặp vô hạn