Hướng Dẫn Breadth-First Search (BFS) Cho Người Mới Bắt Đầu

1. Giới Thiệu

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

Ứng Dụng Thực Tế:

Tìm đường đi ngắn nhất trong mạng lưới giao thông hoặc bản đồ.
Web Crawlers để thu thập dữ liệu từ các trang web.
Tìm kiếm bạn bè trên mạng xã hội (Tìm bạn của bạn bè).

2. Nguyên Lý Hoạt Động

BFS sử dụng một hàng đợi (queue) để quản lý thứ tự duyệt:

Bắt đầu từ một nút gốc.
Đánh dấu nút này là đã thăm và đưa vào hàng đợi.
Lặp lại các bước sau cho đến khi hàng đợi rỗng:
- Lấy một nút ra khỏi hàng đợi.
- Duyệt tất cả các nút kề chưa được thăm, đánh dấu chúng, và đưa vào hàng đợi.

3. Cài Đặt BFS Trong Python

Dưới đây là cách triển khai thuật toán BFS bằng Python với 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')

Giải Thích Code:

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

4. Độ Phức Tạp

Thời gian: O(V + E) (V là số đỉnh, E là số cạnh)
Không gian: O(V) (cần lưu danh sách đỉnh đã thăm và hàng đợi)

5. Tổng Kết

BFS phù hợp để tìm đường đi ngắn nhất trong đồ thị không trọng số.
Sử dụng hàng đợi (queue) để quản lý quá trình duyệt.
Độ phức tạp O(V + E), hiệu quả với đồ thị vừa và nhỏ.

Bạn có thể thử nghiệm với các đồ thị lớn hơn để hiểu rõ hơn về BFS!

Algorithm