Duyệt sâu (DFS)

Khái niệm

Duyệt theo chiều sâu (Depth-First Search — DFS) khám phá một nhánh đồ thị/cây đến hết trước khi quay lại và thử nhánh khác. Cơ chế này tự nhiên được cài đặt bằng đệ quy hoặc stack.

Ứng dụng phổ biến:

Duyệt toàn bộ đồ thị/cây
Phát hiện chu trình
Tìm thành phần liên thông
Tô màu đồ thị (kiểm tra hai phía)
Bài toán backtracking (quay lui)

Biểu diễn đồ thị

Đồ thị có thể lưu dưới dạng danh sách kề (adjacency list):

# Đồ thị vô hướng — danh sách kề
do_thi = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0],
    3: [1],
    4: [1, 5],
    5: [4]
}
#    0
#   / \
#  1   2
# / \
# 3   4
#     |
#     5

Cài đặt DFS bằng đệ quy

def dfs_de_quy(do_thi, u, da_tham=None):
    if da_tham is None:
        da_tham = set()
    da_tham.add(u)
    print(u, end=" ")
    for v in do_thi.get(u, []):
        if v not in da_tham:
            dfs_de_quy(do_thi, v, da_tham)
    return da_tham

do_thi = {0:[1,2], 1:[0,3,4], 2:[0], 3:[1], 4:[1,5], 5:[4]}
print("Thứ tự duyệt DFS từ đỉnh 0:")
dfs_de_quy(do_thi, 0)
# 0 1 3 4 5 2

Cài đặt DFS bằng stack (không đệ quy)

def dfs_stack(do_thi, start):
    da_tham = set()
    stack = [start]
    thu_tu = []

    while stack:
        u = stack.pop()
        if u in da_tham:
            continue
        da_tham.add(u)
        thu_tu.append(u)
        for v in reversed(do_thi.get(u, [])):   # Đảo để giữ thứ tự trái-phải
            if v not in da_tham:
                stack.append(v)

    return thu_tu

do_thi = {0:[1,2], 1:[0,3,4], 2:[0], 3:[1], 4:[1,5], 5:[4]}
print(dfs_stack(do_thi, 0))   # [0, 1, 3, 4, 5, 2]

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

Dễ — Đếm số thành phần liên thông

Đếm số “nhóm” tách biệt trong đồ thị — mỗi lần DFS từ một đỉnh chưa thăm là một thành phần mới.

def dem_thanh_phan_lien_thong(n, canh):
    """
    n: số đỉnh (0 đến n-1)
    canh: [(u, v)] — danh sách cạnh vô hướng
    """
    do_thi = {i: [] for i in range(n)}
    for u, v in canh:
        do_thi[u].append(v)
        do_thi[v].append(u)

    da_tham = set()
    so_thanh_phan = 0

    for u in range(n):
        if u not in da_tham:
            so_thanh_phan += 1
            # DFS từ u
            stack = [u]
            while stack:
                node = stack.pop()
                if node not in da_tham:
                    da_tham.add(node)
                    for v in do_thi[node]:
                        if v not in da_tham:
                            stack.append(v)

    return so_thanh_phan

print(dem_thanh_phan_lien_thong(5, [(0,1),(1,2),(3,4)]))  # 2
print(dem_thanh_phan_lien_thong(4, []))                    # 4
print(dem_thanh_phan_lien_thong(3, [(0,1),(1,2),(2,0)]))  # 1

Trung bình — DFS trên lưới 2D (flood fill)

Lan màu từ ô nguồn — thay toàn bộ vùng liên thông cùng màu thành màu mới.

def flood_fill(luoi, sr, sc, mau_moi):
    """
    Lan màu từ (sr, sc). Tất cả ô liên thông có cùng màu gốc
    đều được đổi thành mau_moi.
    """
    rows, cols = len(luoi), len(luoi[0])
    mau_goc = luoi[sr][sc]
    if mau_goc == mau_moi:
        return luoi

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if luoi[r][c] != mau_goc:
            return
        luoi[r][c] = mau_moi
        dfs(r + 1, c); dfs(r - 1, c)
        dfs(r, c + 1); dfs(r, c - 1)

    dfs(sr, sc)
    return luoi

luoi = [
    [1, 1, 1],
    [1, 1, 0],
    [1, 0, 1]
]
print(flood_fill(luoi, 1, 1, 2))
# [[2, 2, 2],
#  [2, 2, 0],
#  [2, 0, 1]]

Khó — Tìm tất cả đường đi từ nguồn đến đích

def tim_all_paths(do_thi, start, end):
    """
    Tìm tất cả đường đi từ start đến end trong đồ thị có hướng.
    Dùng DFS + backtracking.
    """
    all_paths = []

    def dfs(u, path, da_tham):
        if u == end:
            all_paths.append(path[:])   # Lưu bản sao đường đi
            return
        for v in do_thi.get(u, []):
            if v not in da_tham:
                da_tham.add(v)
                path.append(v)
                dfs(v, path, da_tham)
                path.pop()              # Backtrack
                da_tham.remove(v)

    dfs(start, [start], {start})
    return all_paths

do_thi = {0:[1,2], 1:[3], 2:[3], 3:[]}   # Đồ thị có hướng
paths = tim_all_paths(do_thi, 0, 3)
for p in paths:
    print(p)
# [0, 1, 3]
# [0, 2, 3]

Kết luận

DFS là nền tảng cho vô số thuật toán đồ thị nâng cao: topological sort, phát hiện chu trình, Tarjan’s SCC, và nhiều bài backtracking (N-Queens, sudoku solver, tổ hợp-hoán vị). Để học sâu hơn về ứng dụng DFS trên đồ thị thực tế, xem Sắp xếp tô pô trong mục Lý thuyết đồ thị. Tiếp theo hãy học BFS — tìm đường đi ngắn nhất trên đồ thị không có trọng số.

Trong series này: