BFS & DFS — Duyệt đồ thị

Mỗi khi Google crawl trang web, mỗi khi garbage collector quét heap để tìm object còn sống, mỗi khi LinkedIn gợi ý "People You May Know" — đằng sau đều là BFS hoặc DFS. Hai thuật toán này là nền móng của mọi thao tác trên đồ thị.

Hiểu rõ BFS và DFS không chỉ giúp bạn giải bài tập duyệt đồ thị, mà còn cho bạn hai mô hình tư duy khác nhau để tiếp cận bất kỳ bài toán khám phá nào: khám phá theo lớp (layered exploration) và khám phá đến tận cùng (exhaustive deep dive).

Bức tranh tư duy

BFS — Sóng lan trên mặt nước. Ném một viên đá xuống hồ. Gợn sóng lan ra đồng tâm — lớp 1, lớp 2, lớp 3. BFS thăm tất cả đỉnh cách nguồn 1 cạnh trước, rồi mới đến các đỉnh cách 2 cạnh, 3 cạnh... Kết quả: luôn tìm được đường đi ngắn nhất về số cạnh.

DFS — Đi sâu vào hang động. Bạn cầm đèn pin đi vào một hang động phân nhánh. Tại mỗi ngã rẽ, bạn chọn một hướng và đi đến tận cùng. Khi gặp ngõ cụt, bạn quay lui về ngã rẽ gần nhất chưa khám phá và thử hướng khác. Kết quả: khám phá triệt để từng nhánh.

BFS (sóng lan):                    DFS (hang động):
    1                                  1
   / \                                / \
  2   3    ← lớp 1                   2   5
 / \   \                            /     \
4   5   6  ← lớp 2                 3       6
                                    |
Thứ tự: 1 → 2,3 → 4,5,6            4
                                   Thứ tự: 1 → 2 → 3 → 4 → 5 → 6

Lưu ý: analogy "sóng lan" chỉ chính xác trên đồ thị không trọng số. Khi có trọng số khác nhau, BFS không đảm bảo shortest path — lúc đó cần Dijkstra.

Cốt lõi kỹ thuật

BFS — Breadth-First Search

BFS sử dụng hàng đợi (Queue, FIFO) để duy trì thứ tự khám phá theo lớp. Mỗi đỉnh được đánh dấu visited ngay khi đưa vào queue — không phải khi lấy ra — để tránh xử lý trùng.

C++PythonJavaGo

cpp

#include <vector>
#include <queue>
using namespace std;

vector<int> bfs(int src, const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    vector<int> order;
    queue<int> q;

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

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);

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

python

from collections import deque

def bfs(src: int, adj: list[list[int]]) -> list[int]:
    n = len(adj)
    visited = [False] * n
    order = []
    q = deque([src])
    visited[src] = True

    while q:
        u = q.popleft()
        order.append(u)

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

    return order

java

import java.util.*;

public class GraphTraversal {
    public static List<Integer> bfs(int src, List<List<Integer>> adj) {
        int n = adj.size();
        boolean[] visited = new boolean[n];
        List<Integer> order = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();

        visited[src] = true;
        q.add(src);

        while (!q.isEmpty()) {
            int u = q.poll();
            order.add(u);

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

func bfs(src int, adj [][]int) []int {
    n := len(adj)
    visited := make([]bool, n)
    order := []int{}
    queue := []int{src}
    visited[src] = true

    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        order = append(order, u)

        for _, v := range adj[u] {
            if !visited[v] {
                visited[v] = true
                queue = append(queue, v)
            }
        }
    }
    return order
}

DFS — Depth-First Search

DFS sử dụng ngăn xếp (Stack, LIFO) — hoặc tận dụng call stack của đệ quy. Phiên bản đệ quy ngắn gọn hơn, nhưng phiên bản iterative an toàn hơn với đồ thị lớn (tránh stack overflow).

DFS đệ quy:

C++PythonJavaGo

cpp

void dfsRecursive(int u, const vector<vector<int>>& adj,
                  vector<bool>& visited, vector<int>& order) {
    visited[u] = true;
    order.push_back(u);

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

python

def dfs_recursive(u: int, adj: list[list[int]],
                  visited: list[bool], order: list[int]) -> None:
    visited[u] = True
    order.append(u)

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

java

public static void dfsRecursive(int u, List<List<Integer>> adj,
                                boolean[] visited, List<Integer> order) {
    visited[u] = true;
    order.add(u);

    for (int v : adj.get(u)) {
        if (!visited[v]) {
            dfsRecursive(v, adj, visited, order);
        }
    }
}

func dfsRecursive(u int, adj [][]int, visited []bool, order *[]int) {
    visited[u] = true
    *order = append(*order, u)

    for _, v := range adj[u] {
        if !visited[v] {
            dfsRecursive(v, adj, visited, order)
        }
    }
}

DFS iterative (an toàn cho đồ thị lớn):

C++PythonJavaGo

cpp

vector<int> dfsIterative(int src, const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    vector<int> order;
    stack<int> st;
    st.push(src);

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        order.push_back(u);

        // Duyệt ngược để giữ thứ tự giống đệ quy
        for (int i = adj[u].size() - 1; i >= 0; --i) {
            if (!visited[adj[u][i]]) {
                st.push(adj[u][i]);
            }
        }
    }
    return order;
}

python

def dfs_iterative(src: int, adj: list[list[int]]) -> list[int]:
    n = len(adj)
    visited = [False] * n
    order = []
    stack = [src]

    while stack:
        u = stack.pop()
        if visited[u]:
            continue
        visited[u] = True
        order.append(u)

        for v in reversed(adj[u]):
            if not visited[v]:
                stack.append(v)

    return order

java

public static List<Integer> dfsIterative(int src, List<List<Integer>> adj) {
    int n = adj.size();
    boolean[] visited = new boolean[n];
    List<Integer> order = new ArrayList<>();
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(src);

    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (visited[u]) continue;
        visited[u] = true;
        order.add(u);

        List<Integer> neighbors = adj.get(u);
        for (int i = neighbors.size() - 1; i >= 0; i--) {
            if (!visited[neighbors.get(i)]) {
                stack.push(neighbors.get(i));
            }
        }
    }
    return order;
}

func dfsIterative(src int, adj [][]int) []int {
    n := len(adj)
    visited := make([]bool, n)
    order := []int{}
    stack := []int{src}

    for len(stack) > 0 {
        u := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if visited[u] {
            continue
        }
        visited[u] = true
        order = append(order, u)

        for i := len(adj[u]) - 1; i >= 0; i-- {
            if !visited[adj[u][i]] {
                stack = append(stack, adj[u][i])
            }
        }
    }
    return order
}

Đếm thành phần liên thông (Connected Components)

Gọi BFS/DFS từ mỗi đỉnh chưa visited. Mỗi lần gọi khám phá trọn một thành phần.

C++PythonJavaGo

cpp

int countComponents(int n, const vector<vector<int>>& adj) {
    vector<bool> visited(n, false);
    int components = 0;

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            ++components;
            // Dùng BFS hoặc DFS đều được
            queue<int> q;
            q.push(i);
            visited[i] = true;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : adj[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        q.push(v);
                    }
                }
            }
        }
    }
    return components;
}

python

def count_components(n: int, adj: list[list[int]]) -> int:
    visited = [False] * n
    components = 0

    for i in range(n):
        if not visited[i]:
            components += 1
            stack = [i]
            while stack:
                u = stack.pop()
                if visited[u]:
                    continue
                visited[u] = True
                for v in adj[u]:
                    if not visited[v]:
                        stack.append(v)

    return components

java

public static int countComponents(int n, List<List<Integer>> adj) {
    boolean[] visited = new boolean[n];
    int components = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            components++;
            Queue<Integer> q = new LinkedList<>();
            q.add(i);
            visited[i] = true;
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : adj.get(u)) {
                    if (!visited[v]) {
                        visited[v] = true;
                        q.add(v);
                    }
                }
            }
        }
    }
    return components;
}

func countComponents(n int, adj [][]int) int {
    visited := make([]bool, n)
    components := 0

    for i := 0; i < n; i++ {
        if !visited[i] {
            components++
            queue := []int{i}
            visited[i] = true
            for len(queue) > 0 {
                u := queue[0]
                queue = queue[1:]
                for _, v := range adj[u] {
                    if !visited[v] {
                        visited[v] = true
                        queue = append(queue, v)
                    }
                }
            }
        }
    }
    return components
}

Phát hiện chu trình (Cycle Detection)

Trong đồ thị có hướng, DFS phát hiện chu trình bằng cách theo dõi đỉnh đang nằm trên recursion stack hiện tại. Nếu gặp lại đỉnh đang trong stack → có chu trình.

C++PythonJavaGo

cpp

bool hasCycleDFS(int u, const vector<vector<int>>& adj,
                 vector<int>& color) {
    color[u] = 1; // 1 = đang xử lý (gray)
    for (int v : adj[u]) {
        if (color[v] == 1) return true;      // Back edge → cycle
        if (color[v] == 0 && hasCycleDFS(v, adj, color))
            return true;
    }
    color[u] = 2; // 2 = hoàn thành (black)
    return false;
}

bool hasCycle(int n, const vector<vector<int>>& adj) {
    vector<int> color(n, 0); // 0 = chưa thăm (white)
    for (int i = 0; i < n; ++i)
        if (color[i] == 0 && hasCycleDFS(i, adj, color))
            return true;
    return false;
}

python

def has_cycle(n: int, adj: list[list[int]]) -> bool:
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def dfs(u: int) -> bool:
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:
                return True   # Back edge → cycle
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False

    return any(color[i] == WHITE and dfs(i) for i in range(n))

java

public static boolean hasCycle(int n, List<List<Integer>> adj) {
    int[] color = new int[n]; // 0=white, 1=gray, 2=black

    for (int i = 0; i < n; i++)
        if (color[i] == 0 && dfsHasCycle(i, adj, color))
            return true;
    return false;
}

private static boolean dfsHasCycle(int u, List<List<Integer>> adj, int[] color) {
    color[u] = 1;
    for (int v : adj.get(u)) {
        if (color[v] == 1) return true;
        if (color[v] == 0 && dfsHasCycle(v, adj, color)) return true;
    }
    color[u] = 2;
    return false;
}

func hasCycle(n int, adj [][]int) bool {
    color := make([]int, n) // 0=white, 1=gray, 2=black

    var dfs func(u int) bool
    dfs = func(u int) bool {
        color[u] = 1
        for _, v := range adj[u] {
            if color[v] == 1 {
                return true
            }
            if color[v] == 0 && dfs(v) {
                return true
            }
        }
        color[u] = 2
        return false
    }

    for i := 0; i < n; i++ {
        if color[i] == 0 && dfs(i) {
            return true
        }
    }
    return false
}

Thực chiến

Tình huống 1: Web Crawler (BFS theo level)

Bối cảnh: Hệ thống indexing cần crawl các trang web bắt đầu từ seed URL, mở rộng dần theo độ sâu. Giới hạn tối đa maxDepth bước liên kết để tránh crawl vô hạn.

Mục tiêu: Thu thập tất cả URL reachable trong maxDepth hop.

python

from collections import deque

def crawl_bfs(seed_url: str, max_depth: int,
              fetch_links) -> dict[str, int]:
    """
    BFS web crawler giới hạn theo depth.
    Returns: {url: depth} cho tất cả URL đã crawl.
    """
    visited = {seed_url: 0}
    queue = deque([(seed_url, 0)])

    while queue:
        url, depth = queue.popleft()
        if depth >= max_depth:
            continue

        try:
            links = fetch_links(url)
        except Exception:
            continue  # Skip unreachable pages

        for link in links:
            if link not in visited:
                visited[link] = depth + 1
                queue.append((link, depth + 1))

    return visited

Phân tích: BFS đảm bảo mỗi URL được gán đúng depth tối thiểu. Nếu dùng DFS, một nhánh sâu có thể chiếm hết thời gian trước khi explorer các nhánh nông hơn.

Tình huống 2: Garbage Collection — DFS Reachability

Bối cảnh: Garbage collector cần xác định object nào còn "sống" (reachable từ root set) để giải phóng memory cho các object "chết".

Mục tiêu: Đánh dấu tất cả object reachable từ root, phần còn lại sẽ được thu hồi.

python

def mark_reachable(roots: list[int], references: list[list[int]]) -> set[int]:
    """
    DFS mark phase: đánh dấu tất cả object reachable từ root set.
    references[i] = list các object mà object i tham chiếu đến.
    """
    alive = set()

    def dfs(obj: int) -> None:
        if obj in alive:
            return
        alive.add(obj)
        for ref in references[obj]:
            dfs(ref)

    for root in roots:
        dfs(root)

    return alive

Phân tích: DFS phù hợp vì chỉ cần biết reachable hay không, không cần khoảng cách. DFS tiêu thụ ít memory hơn BFS khi đồ thị tham chiếu sâu nhưng mỗi node ít con.

Sai lầm điển hình

❌ Sai lầm 1: Đánh dấu visited khi lấy ra khỏi queue (BFS)

Vấn đề: Đánh dấu visited khi dequeue thay vì khi enqueue.

python

# SAI: đánh dấu khi dequeue
while queue:
    u = queue.popleft()
    visited[u] = True    # Quá muộn!
    for v in adj[u]:
        if not visited[v]:
            queue.append(v)

Tại sao sai: Một đỉnh có thể được thêm vào queue nhiều lần trước khi được lấy ra, gây xử lý trùng lặp và tăng time complexity từ $O (V + E)$ lên $O (V \times E)$ trong worst case.

python

# ĐÚNG: đánh dấu ngay khi enqueue
while queue:
    u = queue.popleft()
    for v in adj[u]:
        if not visited[v]:
            visited[v] = True   # Đánh dấu TRƯỚC khi push
            queue.append(v)

❌ Sai lầm 2: Dùng DFS đệ quy trên đồ thị lớn

Vấn đề: Đồ thị có hàng triệu đỉnh trên một đường thẳng (path graph) gây stack overflow.

python

# SAI: đệ quy trên đồ thị sâu
def dfs(u, adj, visited):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v, adj, visited)  # Stack depth = O(V) → crash

Tại sao sai: Python mặc định giới hạn recursion depth ~1000. C++ và Java cũng giới hạn stack size. Đồ thị production thường có hàng triệu node.

python

# ĐÚNG: DFS iterative
def dfs(src, adj):
    visited = set()
    stack = [src]
    while stack:
        u = stack.pop()
        if u in visited:
            continue
        visited.add(u)
        for v in adj[u]:
            if v not in visited:
                stack.append(v)

❌ Sai lầm 3: Nhầm lẫn BFS cho đồ thị có trọng số

Vấn đề: Dùng BFS tìm đường ngắn nhất trên đồ thị có trọng số khác nhau.

python

# SAI: BFS không tìm shortest path khi cạnh có trọng số khác nhau
#   A --1-- B --1-- D
#   |               ^
#   +------10-------+
# BFS từ A: tìm A→D (10), bỏ qua A→B→D (2)

Tại sao sai: BFS tối ưu về số cạnh, không phải tổng trọng số. Đường A→D có 1 cạnh (weight 10) nên BFS thăm trước, nhưng A→B→D (weight 2) mới là ngắn nhất.

ĐÚNG: Dùng Dijkstra cho đồ thị có trọng số ≥ 0.
       Dùng Bellman-Ford nếu có trọng số âm.

❌ Sai lầm 4: Quên xử lý đồ thị không liên thông

Vấn đề: Chỉ gọi BFS/DFS từ một đỉnh nguồn, bỏ sót các thành phần liên thông khác.

python

# SAI: chỉ duyệt từ đỉnh 0
bfs(0, adj)  # Bỏ sót các đỉnh không liên thông với 0

Tại sao sai: Trong production, đồ thị thường không liên thông (ví dụ: mạng xã hội có nhiều cluster độc lập).

python

# ĐÚNG: duyệt tất cả thành phần
visited = [False] * n
for i in range(n):
    if not visited[i]:
        bfs(i, adj, visited)

Under the Hood

Hiệu năng

Thuật toán	Time	Space	Ghi chú
BFS	$O (V + E)$	$O (V)$ queue + $O (V)$ visited	Queue có thể chứa $O (V)$ đỉnh trong worst case
DFS (đệ quy)	$O (V + E)$	$O (V)$ call stack + $O (V)$ visited	Stack depth = chiều sâu đồ thị
DFS (iterative)	$O (V + E)$	$O (V)$ stack + $O (V)$ visited	Stack có thể chứa nhiều bản sao đỉnh

Nội bộ triển khai

BFS space analysis: Queue tối đa chứa $O (V)$ đỉnh — worst case xảy ra khi đồ thị là star graph (1 đỉnh trung tâm nối tất cả). Trên đồ thị thưa dạng tree, queue chứa tối đa ~width of tree.

DFS iterative vs recursive: Phiên bản iterative có thể push cùng một đỉnh nhiều lần vào stack (khi nhiều đỉnh cùng trỏ đến nó). Điều này không ảnh hưởng time complexity nhờ visited check, nhưng stack tạm thời có thể lớn hơn $O (V)$ . Phiên bản recursive tránh được điều này nhưng đổi lại bị giới hạn call stack.

Adjacency list vs matrix: Với adjacency matrix, duyệt đỉnh kề tốn $O (V)$ thay vì $O (\deg (u))$ , nên tổng complexity trở thành $O (V^{2})$ — chấp nhận được với dense graph nhưng rất chậm với sparse graph.

Trade-offs

Tiêu chí	BFS	DFS
Shortest path (không trọng số)	✅ Đảm bảo	❌ Không đảm bảo
Memory trên đồ thị rộng	❌ Queue lớn	✅ Stack nhỏ hơn
Memory trên đồ thị sâu	✅ Queue nhỏ	❌ Stack/recursion sâu
Topological sort	✅ Kahn's algorithm	✅ Reverse post-order
Cycle detection (có hướng)	Phức tạp hơn	✅ Tự nhiên (back edge)
Duyệt theo level	✅ Native	❌ Cần thêm logic

Checklist ghi nhớ

✅ Checklist triển khai

Cài đặt BFS

[ ] Đánh dấu visited khi enqueue, không phải khi dequeue
[ ] Dùng deque (Python) hoặc queue (C++) — không dùng list cho BFS
[ ] Xử lý đồ thị không liên thông: lặp qua tất cả đỉnh chưa visited

Cài đặt DFS

[ ] Dùng iterative cho đồ thị lớn (> 10K đỉnh) để tránh stack overflow
[ ] Dùng 3-color (white/gray/black) cho cycle detection trên đồ thị có hướng
[ ] Đảo thứ tự neighbor khi push vào stack nếu cần giữ đúng thứ tự duyệt

Chọn BFS hay DFS

[ ] Cần shortest path (không trọng số) → BFS
[ ] Cần cycle detection trên đồ thị có hướng → DFS
[ ] Đồ thị rất sâu, ít rộng → BFS an toàn hơn về memory
[ ] Đồ thị rất rộng, ít sâu → DFS an toàn hơn về memory

Bài tập luyện tập

Bài 1: Số đảo (Number of Islands) — Foundation

Đề bài: Cho lưới 2D gồm '1' (đất) và '0' (nước). Đếm số đảo. Một đảo là một nhóm '1' liên thông theo 4 hướng (trên, dưới, trái, phải).

🧠 Quiz

Câu hỏi: Với lưới m×n, độ phức tạp thời gian của giải thuật đếm đảo bằng BFS/DFS là bao nhiêu?

[ ] A. $O (m \times n \times \log (m \times n))$
[x] B. $O (m \times n)$
[ ] C. $O ((m \times n)^{2})$
[ ] D. $O (m + n)$ Giải thích: Mỗi ô được thăm tối đa 1 lần. Tổng số ô là $m \times n$ . Mỗi ô kiểm tra 4 neighbor → tổng work là $O (4 \times m \times n) = O (m \times n)$ .

💡 Gợi ý

Mỗi ô '1' chưa visited là seed của một đảo mới
Từ seed, dùng BFS/DFS để đánh dấu toàn bộ đảo

✅ Lời giải

python

def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

    m, n = len(grid), len(grid[0])
    count = 0

    def dfs(r: int, c: int) -> None:
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != '1':
            return
        grid[r][c] = '0'  # Đánh dấu visited bằng cách sink
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)

    return count

Phân tích: Time $O (m \times n)$ , Space $O (m \times n)$ worst case cho recursion stack. Kỹ thuật "sink island" (đổi '1' thành '0') giúp tiết kiệm mảng visited riêng.

Bài 2: Bipartite Check — Intermediate

Đề bài: Kiểm tra xem đồ thị vô hướng có phải đồ thị hai phía (bipartite) không. Đồ thị bipartite có thể tô bằng 2 màu sao cho không có 2 đỉnh kề cùng màu.

💡 Gợi ý

BFS/DFS tô màu: tô đỉnh nguồn màu 0, tất cả neighbor màu 1, neighbor của neighbor màu 0...
Nếu gặp neighbor đã tô cùng màu → không bipartite

✅ Lời giải

python

from collections import deque

def is_bipartite(n: int, adj: list[list[int]]) -> bool:
    color = [-1] * n

    for start in range(n):
        if color[start] != -1:
            continue
        queue = deque([start])
        color[start] = 0

        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    return False

    return True

Phân tích: Time $O (V + E)$ , Space $O (V)$ . Ứng dụng: job assignment, graph coloring, matching problems.

Liên kết học tiếp

Từ khóa glossary: BFS, DFS, breadth-first search, depth-first search, duyệt đồ thị, connected components, cycle detection, graph traversal

Tìm kiếm liên quan: duyệt theo chiều rộng, duyệt theo chiều sâu, tìm thành phần liên thông, phát hiện chu trình

BFS & DFS — Duyệt đồ thị ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

BFS — Breadth-First Search ​

DFS — Depth-First Search ​

Đếm thành phần liên thông (Connected Components) ​

Phát hiện chu trình (Cycle Detection) ​

Thực chiến ​

Tình huống 1: Web Crawler (BFS theo level) ​

Tình huống 2: Garbage Collection — DFS Reachability ​

Sai lầm điển hình ​

❌ Sai lầm 1: Đánh dấu visited khi lấy ra khỏi queue (BFS) ​

❌ Sai lầm 2: Dùng DFS đệ quy trên đồ thị lớn ​

❌ Sai lầm 3: Nhầm lẫn BFS cho đồ thị có trọng số ​

❌ Sai lầm 4: Quên xử lý đồ thị không liên thông ​

Under the Hood ​

Hiệu năng ​

Nội bộ triển khai ​

Trade-offs ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Số đảo (Number of Islands) — Foundation ​

Bài 2: Bipartite Check — Intermediate ​

Liên kết học tiếp ​

BFS & DFS — Duyệt đồ thị

Bức tranh tư duy

Cốt lõi kỹ thuật

BFS — Breadth-First Search

DFS — Depth-First Search

Đếm thành phần liên thông (Connected Components)

Phát hiện chu trình (Cycle Detection)

Thực chiến

Tình huống 1: Web Crawler (BFS theo level)

Tình huống 2: Garbage Collection — DFS Reachability

Sai lầm điển hình

❌ Sai lầm 1: Đánh dấu visited khi lấy ra khỏi queue (BFS)

❌ Sai lầm 2: Dùng DFS đệ quy trên đồ thị lớn

❌ Sai lầm 3: Nhầm lẫn BFS cho đồ thị có trọng số

❌ Sai lầm 4: Quên xử lý đồ thị không liên thông

Under the Hood

Hiệu năng

Nội bộ triển khai

Trade-offs

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Số đảo (Number of Islands) — Foundation

Bài 2: Bipartite Check — Intermediate

Liên kết học tiếp