Thuật toán DFS (duyệt theo chiều sâu) là gì: cách hoạt động, code và độ phức tạp

DFS giải bài toán gì

DFS trả lời câu hỏi “từ đây có thể đến được đâu?” bằng cách khám phá trọn một nhánh trước khi sang nhánh khác. Thứ tự này hữu ích khi cấu trúc của các đường đi quan trọng hơn độ dài của chúng: tìm lối ra khỏi mê cung, kiểm tra đồ thị có chu trình hay không, sắp xếp các công việc phụ thuộc nhau, hoặc liệt kê mọi lời giải của một câu đố.

Khác với duyệt theo chiều rộng, DFS không tìm đường đi ngắn nhất. Điểm mạnh của nó là chỉ cần giữ đường đi hiện tại trong bộ nhớ và tự nhiên ghi lại thời điểm vào nút cũng như thời điểm hoàn tất nút.

Ý tưởng bằng lời đơn giản

1. Đánh dấu nút hiện tại là đã thăm.
2. Với mỗi nút kề chưa thăm, di chuyển tới đó và lặp lại bước 1 từ nút ấy.
3. Khi một nút không còn nút kề nào chưa thăm, nút đó đã hoàn tất: quay về nút mà bạn đã đi từ đó đến.
4. Khi quay về nút xuất phát và nó không còn nút kề chưa thăm, cuộc tìm kiếm kết thúc.

Việc quay về nút trước đó gọi là quay lui (backtracking). Với đệ quy, ngăn xếp lời gọi làm việc này giúp bạn.

Ví dụ từng bước

Dùng lại đồ thị vô hướng trong bài về BFS: A–B, A–C, B–D, C–D, C–E, D–F. Bắt đầu từ A và thử các nút kề theo thứ tự bảng chữ cái.

Thứ tự thăm là A, B, D, C, E, F. Thứ tự hoàn tất là E, C, F, D, B, A. Sắp xếp tô-pô và các thuật toán tìm thành phần liên thông mạnh dùng thứ tự hoàn tất này.

Cài đặt bằng Python

Phiên bản đệ quy ngắn nhất và gần với ý tưởng nhất:

def dfs(graph, node, visited=None):
    if visited is None:
        visited = []
    visited.append(node)
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(graph, nxt, visited)
    return visited
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(dfs(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

Dùng list giúp ví dụ dễ đọc nhưng phép kiểm tra in có độ phức tạp O(n). Với đồ thị lớn, hãy giữ một set riêng để kiểm tra tư cách thành viên. Phiên bản lặp dùng ngăn xếp tường minh và tránh giới hạn đệ quy của Python. Các nút kề được đẩy vào theo thứ tự ngược để khi lấy ra vẫn đúng thứ tự ban đầu:

def dfs_iterative(graph, start):
    visited, order = set(), []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for nxt in reversed(graph[node]):
            if nxt not in visited:
                stack.append(nxt)
    return order
print(dfs_iterative(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

Lưu ý điểm khác so với BFS: ở đây nút được đánh dấu khi được lấy ra khỏi ngăn xếp, nên nó có thể nằm trong ngăn xếp nhiều lần. Điều này đúng với DFS và giữ đúng thứ tự duyệt sâu thật sự.

Phát hiện chu trình trong đồ thị có hướng

Một ứng dụng kinh điển của DFS là tô màu mỗi nút: trắng (chưa gặp), xám (đang nằm trên đường đi hiện tại) và đen (đã hoàn tất). Chạm tới một nút xám nghĩa là có cạnh quay ngược vào đường đi hiện tại, tức là có chu trình.

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    def visit(node):
        color[node] = GRAY
        for nxt in graph[node]:
            if color[nxt] == GRAY:
                return True              # back edge
            if color[nxt] == WHITE and visit(nxt):
                return True
        color[node] = BLACK
        return False
    return any(color[n] == WHITE and visit(n) for n in graph)
print(has_cycle({"a": ["b"], "b": ["c"], "c": ["a"]}))  # True
print(has_cycle({"a": ["b"], "b": ["c"], "c": []}))     # False

Độ phức tạp thời gian và không gian

Biến thể và lỗi thường gặp

• Pre-order và post-order: ghi lại nút khi vào nút (pre-order) hoặc khi hoàn tất nút (post-order). Thứ tự post-order đảo ngược của đồ thị có hướng không chu trình (DAG) là một thứ tự tô-pô.
• Thành phần liên thông: bắt đầu một lượt DFS mới từ mỗi nút còn chưa thăm; mỗi lần bắt đầu tương ứng một thành phần.
• DFS tăng dần độ sâu (iterative deepening): chạy DFS với giới hạn độ sâu 0, 1, 2, … Cách này tìm được đường đi ngắn nhất như BFS nhưng tốn ít bộ nhớ như DFS.
• Loang màu (flood fill) trên lưới (công cụ đổ màu) là DFS hoặc BFS trên các ô lân cận cùng màu.

Các lỗi thường gặp khác: quên tập đã thăm (vòng lặp vô hạn khi có chu trình), dùng đối số mặc định có thể thay đổi như visited=[] (nó bị dùng chung giữa các lần gọi), và coi cạnh vô hướng quay về nút cha là chu trình.

Khi nào dùng DFS và ứng dụng thực tế

• Dùng DFS cho bài toán khả năng tiếp cận, phát hiện chu trình, sắp xếp tô-pô, thành phần liên thông và liên thông mạnh, cầu và khớp, cũng như tìm kiếm vét cạn bằng quay lui.
• Dùng BFS khi cần ít bước nhất, và dùng Dijkstra hoặc A* khi các cạnh có trọng số.
• Bài phỏng vấn: đếm số đảo, nhân bản đồ thị, course schedule (phát hiện chu trình), tổng đường đi trong cây nhị phân, sinh hoán vị.
• Thực tế: hệ thống build và trình quản lý gói giải quyết thứ tự phụ thuộc, trình biên dịch phân tích luồng điều khiển, sinh mê cung, và duyệt cây trên hệ thống tệp hoặc tài liệu HTML.