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

Bài 12.3 - Cài đặt BFSbằng Python

BFS (Breadth-First Search – Duyệt theo chiều rộng) là một trong những thuật toán cơ bản và quan trọng nhất trong lập trình đồ thị. BFS được sử dụng để duyệt qua tất cả các đỉnh trong một đồ thị bắt đầu từ một đỉnh gốc và mở rộng theo từng lớp.

BFS hoạt động như thế nào?

BFS bắt đầu từ một đỉnh gốc, sau đó:

1. Duyệt các đỉnh lân cận gần nhất (cấp độ 1).
2. Tiếp tục duyệt các đỉnh cấp độ tiếp theo.
3. Lặp lại cho đến khi tất cả các đỉnh có thể truy cập được đã được duyệt.

BFS sử dụng cấu trúc hàng đợi (queue) để lưu trữ các đỉnh chờ được duyệt.

Cấu trúc đồ thị dùng danh sách kề

Trước tiên, ta cần biểu diễn đồ 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ề với nó.

Cài đặt thuật toán BFS bằng Python

from collections import deque

def bfs(graph, start):
    visited = set()             # Tập các đỉnh đã duyệt
    queue = deque([start])      # Hàng đợi lưu các đỉnh cần duyệt

    while queue:
        node = queue.popleft()  # Lấy đỉnh đầu tiên ra khỏi hàng đợi
        if node not in visited:
            print(node)         # Duyệt đỉnh
            visited.add(node)   # Đánh dấu đã duyệt

            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    queue.append(neighbor)  # Thêm các đỉnh kề vào hàng đợi

Ví dụ minh hoạ 1 – Duyệt đồ thị từ đỉnh 'A'

bfs(graph, 'A')

Kết quả:

A
B
C
D
E
F

BFS duyệt từ A, sau đó là B và C, rồi mở rộng đến D, E và F.

Ứng dụng thực tế của BFS

• Tìm đường đi ngắn nhất trong đồ thị không trọng số
• Kiểm tra tính liên thông của đồ thị
• Giải bài toán mê cung hoặc đường đi trong ma trận
• Xây dựng cây tìm kiếm theo lớp

Cải tiến: Tìm đường đi ngắn nhất từ start đến goal

def bfs_shortest_path(graph, start, goal):
    from collections import deque

    visited = set()
    queue = deque([[start]])  # Mỗi phần tử trong queue là một đường đi

    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

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

shortest = bfs_shortest_path(graph, 'A', 'F')
print("Đường đi ngắn nhất:", shortest)

Kết quả:

Đường đi ngắn nhất: ['A', 'C', 'F']

Thuật toán sẽ trả về đường đi ngắn nhất đầu tiên tìm thấy vì BFS duyệt theo từng lớp.

Độ phức tạp của BFS

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

Một số biến thể BFS phổ biến

• BFS trong đồ thị có trọng số bằng nhau
• BFS trong ma trận (di chuyển lên, xuống, trái, phải)
• BFS hai chiều (Bidirectional BFS) – tăng tốc độ tìm kiếm
• BFS có giới hạn độ sâu

Tổng kết

• BFS là một thuật toán duyệt đồ thị theo từng lớp, rất hữu ích để tìm đường đi ngắn nhất hoặc duyệt đồ thị rộng.
• Cài đặt đơn giản, dễ mở rộng, rất phù hợp cho người mới bắt đầu học về đồ thị.