Hướng Dẫn Chi Tiết Thuật Toán Duyệt Theo Chiều Rộng (BFS) Dành Cho Người Mới Bắt Đầu

1. Giới Thiệu

Duyệt theo chiều rộng (Breadth-First Search - BFS) là một thuật toán quan trọng trong lập trình, được dùng để thăm hoặc tìm kiếm trên cây hoặc đồ thị. Trong khi các thuật toán có thể duyệt theo chiều sâu, BFS duyệt theo chiều rộng, nghĩa là nó sẽ thăm tất cả các đỉnh ở mức hiện tại trước khi tiếp tục thăm các đỉnh ở mức tiếp theo.

1.1. Các Ứng Dụng Thực Tế Của BFS:

• Tìm đường đi ngắn nhất trong các mạng lưới giao thông, bảo đảm tìm kiếm một cách hiệu quả trên bản đồ.
• Crawl web để thu thập dữ liệu từ các trang web. Đây là phương pháp chính được sử dụng bởi các công cụ tìm kiếm.
• Tìm kiếm bạn bè trên mạng xã hội, cho phép người dùng tìm kiếm bạn bè của bạn bè một cách dễ dàng.

2. Nguyên Lý Hoạt Động Của Thuật Toán BFS

BFS hoạt động dựa trên hàng đợi (queue) để quản lý thứ tự duyệt các đỉnh:

1. Bắt đầu từ một nút gốc (nút xuất phát).
2. Đánh dấu nút này là đã thăm và đưa nó vào hàng đợi.
3. Tiến hành lặp lại các bước cho đến khi hàng đợi trở nên rỗng:
   • Lấy nút đầu tiên ra khỏi hàng đợi.
   • Duyệt qua tất cả các nút kề chưa được thăm, đánh dấu chúng là đã thăm và đưa vào hàng đợi.

3. Cách Cài Đặt Thuật Toán BFS Bằng Python

Dưới đây là cách bạn có thể triển khai thuật toán BFS bằng Python sử dụng cấu trúc dữ liệu danh sách kề (adjacency list):

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            queue.extend(graph[node])

# Ví dụ về đồ thị dưới dạng danh sách kề
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("Kết quả duyệt BFS từ đỉnh A:")
bfs(graph, 'A')

3.1. Giải Thích Mã Nguồn:

• queue: Hàng đợi được sử dụng để lưu trữ các nút sẽ được thăm tiếp theo.
• visited: Tập hợp chứa các nút đã được thăm, ngăn ngừa việc thăm lại.
• Vòng lặp duyệt đồ thị: Lấy phần tử đầu tiên trong hàng đợi, in ra, và thêm tất cả các nút kề chưa được thăm vào hàng đợi.

4. Phân Tích Độ Phức Tạp Của Thuật Toán BFS

• Độ Phức Tạp Thời Gian: O(V + E), với V là số đỉnh và E là số cạnh của đồ thị.
• Độ Phức Tạp Không Gian: O(V), do cần lưu trữ danh sách các đỉnh đã thăm và hàng đợi.

5. Tổng Kết

Thuật toán BFS là một công cụ mạnh mẽ để tìm đường đi ngắn nhất trong các đồ thị không trọng số. Phương pháp này sử dụng hàng đợi để quản lý quá trình duyệt các đỉnh, đồng thời có độ phức tạp O(V + E), rất phù hợp với các đồ thị có kích thước vừa và nhỏ. Bạn có thể thử nghiệm với các đồ thị lớn hơn để làm quen hơn với phương pháp này!

source: viblo