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

Bài 12.4 - Tìm đường đi trong đồ thị với Python

Tìm đường đi trong đồ thị là một bài toán phổ biến trong lập trình, thường được áp dụng trong:

• Tìm đường trong mê cung
• Tìm đường đi từ A đến B trong bản đồ
• Kiểm tra kết nối giữa hai điểm trong mạng lưới

Trong bài này, chúng ta sẽ học cách tìm đường đi từ một đỉnh start đến một đỉnh goal trong đồ thị không trọng số, sử dụng BFS và DFS.

Biểu diễn đồ thị bằng danh sách kề

Chúng ta sẽ sử dụng cấu trúc dict để lưu trữ đồ thị:

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

Mỗi đỉnh là một key, và giá trị là danh sách các đỉnh kề (có thể đi đến).

Tìm đường đi bằng DFS (đệ quy)

def dfs_path(graph, start, goal, path=None, visited=None):
    if path is None:
        path = [start]
    if visited is None:
        visited = set()

    visited.add(start)

    if start == goal:
        return path

    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            new_path = dfs_path(graph, neighbor, goal, path + [neighbor], visited)
            if new_path:
                return new_path
    return None

Giải thích:

• visited: để tránh lặp vô hạn (nếu có chu trình).
• path: lưu đường đi hiện tại.
• Dừng lại ngay khi tìm thấy goal.

Ví dụ minh hoạ 1 – DFS tìm đường từ A đến F

result = dfs_path(graph, 'A', 'F')
print("Đường đi bằng DFS:", result)

Kết quả:

Đường đi bằng DFS: ['A', 'B', 'E', 'F']

DFS đi sâu vào từng nhánh, có thể không phải đường ngắn nhất nhưng vẫn tìm được một đường hợp lệ.

Tìm đường đi bằng BFS (tìm đường ngắn nhất)

from collections import deque

def bfs_path(graph, start, goal):
    queue = deque([[start]])
    visited = set()

    while queue:
        path = queue.popleft()
        node = path[-1]

        if node == goal:
            return path

        if node not in visited:
            visited.add(node)
            for neighbor in graph.get(node, []):
                new_path = list(path)
                new_path.append(neighbor)
                queue.append(new_path)
    return None

Giải thích:

• Sử dụng queue để duyệt theo lớp.
• Lưu lại đường đi path trong từng bước.
• Dừng khi gặp goal – đảm bảo là đường đi ngắn nhất.

Ví dụ minh hoạ 2 – BFS tìm đường từ A đến F

result = bfs_path(graph, 'A', 'F')
print("Đường đi bằng BFS:", result)

Kết quả:

Đường đi bằng BFS: ['A', 'C', 'F']

BFS luôn tìm ra đường đi ngắn nhất nếu đồ thị không có trọng số.

So sánh DFS và BFS

Gợi ý bài tập thêm

1. In ra tất cả các đường đi từ start đến goal.
2. Áp dụng trên đồ thị có chu trình.
3. Tìm đường đi trong đồ thị có hướng.
4. Tìm đường đi trong ma trận 2D như mê cung.

Tổng kết

• Có thể dùng DFS hoặc BFS để tìm đường đi giữa 2 đỉnh trong đồ thị.
• DFS đi sâu, nhanh nhưng không đảm bảo đường ngắn nhất.
• BFS duyệt theo lớp, đảm bảo tìm đường ngắn nhất trong đồ thị không trọng số.
• Cả hai đều rất hữu ích tuỳ thuộc vào bài toán cụ thể.