BFS & DFS (Duyệt Đồ Thị)

Đây là hai "đôi chân" để bạn có thể đi lại trong thế giới đồ thị.

1. Breadth-First Search (BFS - Duyệt Chiều Rộng)

Visual: Hãy tưởng tượng bạn ném một viên đá xuống mặt hồ yên ả. Các gợn sóng lan ra theo vòng tròn đồng tâm. BFS hoạt động y hệt vậy: nó thăm các đỉnh gần nguồn nhất trước, rồi loang dần ra xa.

• Cấu trúc dữ liệu: Queue (Hàng đợi - FIFO).
• Đặc tính: Luôn tìm được đường đi ngắn nhất (về số cạnh) trong đồ thị không trọng số.

C++

void bfs(int startNode, vector<int> adj[], int n) {
    vector<bool> visited(n, false);
    queue<int> q;

    visited[startNode] = true;
    q.push(startNode);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";

        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

Python

from collections import deque

def bfs(start_node, adj):
    visited = set()
    q = deque([start_node])
    visited.add(start_node)

    while q:
        u = q.popleft()
        print(u, end=" ")

        for v in adj[u]:
            if v not in visited:
                visited.add(v)
                q.append(v)

2. Depth-First Search (DFS - Duyệt Chiều Sâu)

Visual: Giống như bạn đi giải mê cung. Bạn cứ đi con đường hiện tại sâu hết mức có thể. Nếu đụng ngõ cụt, bạn quay lui (backtrack) lại ngã rẽ gần nhất và thử đường khác.

• Cấu trúc dữ liệu: Stack (Ngăn xếp - LIFO) hoặc Đệ quy (Recursion).
• Đặc tính: Dùng để kiểm tra tính liên thông, tìm chu trình, hoặc topo sort.

C++

// Đệ quy
void dfs(int u, vector<int> adj[], vector<bool> &visited) {
    visited[u] = true;
    cout << u << " ";

    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, adj, visited);
        }
    }
}

Python

def dfs(u, adj, visited):
    visited.add(u)
    print(u, end=" ")

    for v in adj[u]:
        if v not in visited:
            dfs(v, adj, visited)