🗺️ Duyệt đồ thị (BFS/DFS)

Khác với mảng hay linked list - nơi thứ tự duyệt gần như chỉ có một cách (từ đầu đến cuối) - một đồ thị không có thứ tự “tự nhiên” nào để duyệt qua tất cả các đỉnh, vì mỗi đỉnh có thể nối với nhiều đỉnh khác theo nhiều hướng. Hai chiến lược nền tảng để duyệt đồ thị một cách có hệ thống, không lặp lại, là BFS và DFS.

BFS - lan rộng theo từng lớp

Breadth-First Search (tìm kiếm theo chiều rộng) thăm các đỉnh theo thứ tự “gần trước, xa sau”: xuất phát từ một đỉnh, thăm hết mọi đỉnh kề với nó trước, rồi mới đến các đỉnh kề của các đỉnh kề đó, cứ thế lan rộng ra như gợn sóng trên mặt nước.

BFS dùng một hàng đợi (queue) để đảm bảo đúng thứ tự “gần trước xa sau”, và một tập visited để tránh thăm lại một đỉnh nhiều lần (quan trọng vì đồ thị, không như cây, có thể có chu trình - đi vòng lại đỉnh đã thăm).

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()      # lấy đỉnh gần nhất chưa xử lý
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)   # đánh dấu ngay khi đưa vào hàng đợi
                queue.append(neighbor)
    return order

Vì mỗi đỉnh và mỗi cạnh chỉ được xét đúng một lần, độ phức tạp là O(n + m) (n đỉnh, m cạnh). Ứng dụng kinh điển nhất của BFS: tìm đường đi ngắn nhất trên đồ thị không trọng số - vì BFS luôn thăm các đỉnh theo đúng thứ tự khoảng cách tăng dần, đỉnh nào được thăm trước chắc chắn gần điểm xuất phát hơn.

DFS - đâm sâu trước, quay lại sau

Depth-First Search (tìm kiếm theo chiều sâu) đi theo một nhánh cho đến khi không thể đi tiếp (gặp ngõ cụt hoặc toàn bộ đỉnh kề đã thăm), rồi mới quay lui (backtrack) về đỉnh gần nhất còn hướng chưa khám phá.

def dfs(graph, start, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(start)
    order.append(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, order)   # đâm sâu theo nhánh này trước
    return order

Đệ quy ở đây thực chất đang mượn call stack của chương trình để “nhớ đường quay lại” - đây cũng là lý do DFS thường được cài bằng đệ quy hoặc bằng một stack tường minh thay vì queue. Độ phức tạp cũng là O(n + m), giống BFS - khác biệt nằm ở thứ tự thăm, không phải ở tốc độ tổng thể.

BFS hay DFS: chọn thế nào?

Tiêu chí	BFS	DFS
Cấu trúc dùng	Queue	Stack (hoặc đệ quy)
Thứ tự thăm	Gần trước, xa sau	Đâm sâu một nhánh trước
Tìm đường đi ngắn nhất (không trọng số)	Phù hợp - đỉnh thăm trước luôn gần hơn	Không đảm bảo tìm đường ngắn nhất
Bộ nhớ đỉnh (worst-case)	Có thể giữ cả một “lớp” rộng trong queue	Chỉ giữ một nhánh sâu trong stack
Liệt kê/đếm mọi thành phần liên thông	Được	Được, thường code gọn hơn nhờ đệ quy

Mẹo

Quy tắc chọn nhanh: cần đường đi ngắn nhất hoặc muốn thăm theo từng “vòng” khoảng cách → BFS. Chỉ cần thăm hết mọi đỉnh có thể tới (không quan tâm khoảng cách), hoặc bài toán tự nhiên mang tính đệ quy (như duyệt cây con) → DFS thường cho code ngắn gọn hơn.

Ứng dụng: Number of Islands

Đề bài: cho một lưới ô vuông gồm 0 (nước) và 1 (đất), đếm số “hòn đảo” - các cụm ô 1 liền kề nhau theo chiều ngang/dọc.

Đây thực chất là bài toán đếm số thành phần liên thông trên một đồ thị ẩn: mỗi ô đất là một đỉnh, hai ô đất liền kề tạo thành một cạnh. Với mỗi ô đất chưa thăm, chạy DFS (hoặc BFS) để “nhấn chìm” toàn bộ hòn đảo chứa nó, tăng biến đếm lên 1, rồi tiếp tục quét ô tiếp theo:

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    visited = set()

    def dfs(r, c):
        if (r < 0 or r >= rows or c < 0 or c >= cols
                or grid[r][c] == "0" or (r, c) in visited):
            return
        visited.add((r, c))
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            dfs(r + dr, c + dc)     # lan ra 4 hướng, "nhấn chìm" cả hòn đảo

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in visited:
                dfs(r, c)
                count += 1           # mỗi lần gọi dfs từ ô mới = 1 hòn đảo
    return count

Mỗi ô chỉ được thăm đúng một lần nhờ tập visited, nên độ phức tạp là O(rows × cols) - tuyến tính theo kích thước lưới, dù về bản chất đang chạy DFS lặp lại nhiều lần.