DFS — Depth-First Search, preorder/postorder, cycle detection

TL;DR: DFS (Depth-First Search) đi sâu vào một nhánh trước khi quay lại thử nhánh khác — cơ chế LIFO qua call stack hoặc explicit stack. Một lần chạy DFS cho ra hai thứ tự: preorder (khi vào đỉnh) và postorder (khi rời đỉnh sau khi xử lý xong toàn bộ con). Đảo ngược postorder trên DAG chính là topological sort. Pitfall lớn nhất: recursive DFS trên chain graph 1 triệu đỉnh gây StackOverflow — phải dùng iterative DFS với explicit stack trên heap thay thế.

BFS lan sóng theo từng level — nó biết "đỉnh nào cách nguồn 3 hop". Nhưng có những bài toán không cần khoảng cách theo level: bạn muốn đi sâu vào một nhánh trước, rồi mới quay lại thử nhánh khác.

Hãy nghĩ đến build dependency graph của Maven: khi kiểm tra xem có circular dependency không, bạn cần đi theo một chain (A phụ thuộc B, B phụ thuộc C, C phụ thuộc...) cho đến khi hoặc thoát hoặc quay lại đỉnh ban đầu — đó là DFS. Hoặc bài toán đếm connected component, topological sort, maze exploration, Tarjan SCC — tất cả đều tự nhiên dùng DFS.

Bài này dạy DFS recursive và iterative, white/gray/black coloring cho cycle detection, preorder vs postorder traversal, và các pattern hay gặp trong production.

1. Analogy — Khám phá mê cung

Hình dung bạn đang khám phá một mê cung lớn. Chiến lược: chọn một hướng và đi sâu nhất có thể theo hướng đó — đến khi gặp ngõ cụt (dead end) hoặc chỗ đã đến rồi. Lúc đó, quay lại điểm rẽ gần nhất và thử hướng khác. Cứ như vậy cho đến khi thăm hết mọi ngóc ngách.

Đây chính xác là LIFO mechanic — bạn luôn quay lại điểm rẽ gần nhất, không phải điểm rẽ đầu tiên. So sánh với BFS: BFS như drone khảo sát từ trên, thăm mọi phòng cách entrance 1 bước trước, rồi 2 bước, rồi 3 bước — không đi sâu vào nhánh nào.

2. Thuật toán DFS — recursive

DFS(G, start):
    visited[v] <- false cho mọi v
    dfsHelper(G, start, visited)

dfsHelper(G, v, visited):
    if visited[v]: return
    visited[v] <- true

    -- xử lý preorder: ngay khi vào đỉnh
    process_preorder(v)

    for each đỉnh u kề v trong G:
        dfsHelper(G, u, visited)

    -- xử lý postorder: sau khi tất cả con xong
    process_postorder(v)

Time: O(V+E) Space: O(V) — call stack sâu tối đa V frame

Trace ví dụ — graph: 0-1, 0-2, 1-3, 1-4. DFS từ đỉnh 0:

Cây gọi đệ quy:
dfsHelper(0)
  -> dfsHelper(1)
       -> dfsHelper(3)  preorder:3, postorder:3
       -> dfsHelper(4)  preorder:4, postorder:4
     postorder:1
  -> dfsHelper(2)       preorder:2, postorder:2
  postorder:0

Thứ tự preorder:  0, 1, 3, 4, 2
Thứ tự postorder: 3, 4, 1, 2, 0

graph TD
    START(("Bắt đầu\ntừ 0")) --> N0["Vào 0\n(preorder: 0)"]
    N0 --> N1["Vào 1\n(preorder: 1)"]
    N1 --> N3["Vào 3\n(preorder: 3)\n(postorder: 3)"]
    N1 --> N4["Vào 4\n(preorder: 4)\n(postorder: 4)"]
    N1 --> OUT1["Rời 1\n(postorder: 1)"]
    N0 --> N2["Vào 2\n(preorder: 2)\n(postorder: 2)"]
    N0 --> OUT0["Rời 0\n(postorder: 0)"]

3. DFS iterative — explicit stack

Recursive DFS dùng JVM call stack. Với graph sâu O(V) frame, risk StackOverflowError là thực tế — chain graph 1 triệu đỉnh sẽ crash. Giải pháp: dùng Stack trên heap làm explicit stack.

dfsIterative(G, start):
    visited[v] <- false cho mọi v
    S <- Stack rỗng
    S.push(start)

    while S không rỗng:
        v <- S.pop()
        if visited[v]: continue        -- có thể vào stack nhiều lần
        visited[v] <- true
        process(v)

        -- push hàng xóm theo thứ tự ngược để giữ thứ tự duyệt
        for each u kề v theo thứ tự ngược:
            if not visited[u]:
                S.push(u)

Time: O(V+E) Space: O(V)

Tại sao push ngược? Recursive DFS xử lý hàng xóm theo thứ tự tự nhiên (0, 1, 2...). Stack là LIFO — nếu push theo thứ tự tự nhiên, hàng xóm cuối sẽ được pop ra trước. Push ngược → hàng xóm đầu tiên được pop trước → cùng thứ tự duyệt với recursive.

Trade-off:

4. Preorder vs Postorder vs Reverse postorder

Một traversal DFS cho ra hai thứ tự khác nhau — preorder và postorder — từ cùng một lần chạy.

dfsHelper(G, v, visited):
    visited[v] <- true
    process_preorder(v)        -- preorder: ngay khi vào đỉnh

    for each đỉnh u kề v:
        if not visited[u]:
            dfsHelper(G, u, visited)

    process_postorder(v)       -- postorder: sau khi TẤT CẢ con xong

Khi nào dùng preorder:

• File system traversal (find, ls -R): in thư mục cha trước khi liệt kê nội dung.
• Copy tree: tạo node cha trước khi clone children.
• Serialize tree structure: parent cần tồn tại trước children.

Khi nào dùng postorder:

• Delete tree: xóa children trước khi xóa cha (tránh dangling reference).
• Evaluate expression tree: cần giá trị của 2 sub-expression (children) trước khi tính operator (cha).
• Dependency resolution: artifact phải build sau khi tất cả dependency của nó đã build xong — postorder DFS trên DAG cho thứ tự đúng.

Reverse postorder (đảo ngược thứ tự postorder) = topological sort của DAG. Đây là cơ sở của DFS-based topological sort — bài 04-topological-sort sẽ phân tích chi tiết.

5. Cycle detection — white/gray/black coloring

Cách phát hiện cycle trên directed graph là dùng 3 màu thay vì boolean visited:

• WHITE: chưa thăm lần nào.
• GRAY: đang trong recursion — đỉnh này đang nằm trên call stack.
• BLACK: đã xong hoàn toàn — đã recurse qua tất cả descendants.

Logic detect cycle: nếu DFS từ đỉnh v gặp hàng xóm u màu GRAY, nghĩa là u đang nằm trên call stack — tức là có đường đi từ u đến v (qua path DFS đang đi) và từ v đến u (cạnh vừa xét). Đây là back-edge → cycle.

hasCycle(G):
    color[v] <- WHITE cho mọi v

    for each v trong G:
        if color[v] = WHITE:
            if dfsCheck(G, v, color): return true
    return false

dfsCheck(G, v, color):
    color[v] <- GRAY               -- đang vào: đỉnh lên stack

    for each đỉnh u kề v:
        if color[u] = GRAY: return true    -- back-edge -> cycle
        if color[u] = WHITE:
            if dfsCheck(G, u, color): return true

    color[v] <- BLACK              -- đang rời: đã xử lý xong
    return false

Time: O(V+E) Space: O(V)

flowchart TD
    ENTER["Vào đỉnh v\n→ tô GRAY"]
    CHECK{"Hàng xóm u\nmàu gì?"}
    GRAY_FOUND["u màu GRAY\n→ back-edge\n→ CÓ CYCLE"]
    WHITE_RECURSE["u màu WHITE\n→ đệ quy DFS(u)"]
    BLACK_SKIP["u màu BLACK\n→ bỏ qua\n(đã xong, không phải cycle)"]
    EXIT["Rời đỉnh v\n→ tô BLACK"]

    ENTER --> CHECK
    CHECK --> GRAY_FOUND
    CHECK --> WHITE_RECURSE
    CHECK --> BLACK_SKIP
    WHITE_RECURSE --> CHECK
    BLACK_SKIP --> CHECK
    CHECK -- "hết hàng xóm" --> EXIT

Tại sao cần GRAY thay vì chỉ visited boolean? Với directed graph, boolean visited không phân biệt được "đang trên stack" vs "đã xử lý xong". GRAY có nghĩa đang trên call stack ngay lúc này. BLACK có nghĩa đã xong, không còn trên stack. Chỉ GRAY mới là back-edge và cycle.

Undirected graph: Cần exclude parent vì trong undirected graph, cùng một cạnh xuất hiện hai chiều trong adjacency list — trở về cha không phải cycle:

dfsCheckUndirected(G, v, parent, visited):
    visited[v] <- true
    for each đỉnh u kề v:
        if not visited[u]:
            if dfsCheckUndirected(G, u, v, visited): return true
        else if u != parent:
            return true           -- back-edge về non-parent -> cycle
    return false

Time: O(V+E) Space: O(V)

6. Connected components — undirected graph

Đếm số connected component trong undirected graph: mỗi lần DFS từ một đỉnh chưa thăm sẽ visit đúng một component (tất cả đỉnh có thể đến được từ đó).

countComponents(G):
    visited[v] <- false cho mọi v
    count <- 0

    for each v trong G:
        if not visited[v]:
            dfsHelper(G, v, visited)   -- visit toàn bộ component chứa v
            count <- count + 1         -- một component mới được tìm thấy

    return count

Time: O(V+E) Space: O(V)

Nếu graph có K component, vòng for sẽ trigger DFS đúng K lần — mỗi lần mark toàn bộ component đó rồi tăng counter. Tổng cộng mỗi đỉnh và cạnh vẫn chỉ được xử lý một lần dù DFS chạy nhiều lần.

7. Pitfall tổng hợp

Pitfall 1 — Stack overflow trên deep graph

-- BUG: recursive DFS trên chain graph 1 triệu đỉnh
-- 0 -> 1 -> 2 -> ... -> 999999
-- Độ sâu call stack = 1.000.000 frame -> crash StackOverflow

-- ĐÚNG: iterative DFS -- stack trên heap, không bị giới hạn
dfsIterative(G, start)    -- xử lý 1 triệu đỉnh thoải mái

Nếu buộc phải dùng recursive, có thể tạo thread riêng với stack size lớn hơn — nhưng đây là workaround, không phải giải pháp. Dùng iterative DFS là giải pháp đúng.

Pitfall 2 — Cycle detection sai trên undirected graph

-- BUG: không track parent -- false positive trên undirected graph
dfsCheckBug(G, v, visited):
    visited[v] <- true
    for each đỉnh u kề v:
        if visited[u]: return true   -- BUG: u có thể chỉ là parent!
    return false

-- Graph: 0 -- 1 -- 2 (không có cycle)
-- DFS từ 0: thăm 1, từ 1 thăm 0 (đã visited) -> báo có cycle -> SAI

Luôn track parent khi detect cycle trên undirected graph. Directed graph dùng white/gray/black (không cần parent vì mọi back-edge đều là cycle thực sự).

Pitfall 3 — Mark visited sai chỗ gây visit nhiều lần

-- BUG: không kiểm tra visited trước khi đệ quy
dfsHelperBug(G, v, visited):
    visited[v] <- true
    for each đỉnh u kề v:
        dfsHelperBug(G, u, visited)   -- không check -- có thể vào u nhiều lần

Với graph có nhiều đường tới cùng một đỉnh, code trên sẽ recurse vào u nhiều lần — exponential time. Kiểm tra visited[u] trước khi gọi đệ quy, hoặc check visited[v] ngay đầu hàm.

8. DFS variants — mở rộng

Iterative deepening DFS (IDDFS): kết hợp memory footprint của DFS với guarantee level-by-level của BFS. Chạy DFS với depth limit 1, rồi 2, rồi 3... Tìm được đỉnh đích ở độ sâu d với memory O(d) thay vì O(b^d) của BFS. Dùng trong AI game tree search (chess engine, puzzle solver).

Tarjan SCC (Strongly Connected Components): tìm tất cả SCC trong directed graph bằng một lần DFS, dùng low-link values để detect khi nào một SCC đã hoàn chỉnh. Complexity O(V + E). Bài nâng cao Module 3.

Articulation points và bridges: một đỉnh là articulation point nếu xóa nó làm graph bị ngắt kết nối. Một cạnh là bridge nếu xóa nó làm graph bị ngắt. Cả hai đều tìm được trong O(V + E) bằng DFS với disc và low arrays. Ứng dụng: phân tích độ bền của network — tìm single point of failure.

9. Applied to tech

Maven / Gradle build dependency cycle detection: Gradle xây dựng DAG từ các implementation dependency, chạy DFS với white/gray/black để kiểm tra cycle. Nếu phát hiện back-edge (màu GRAY), Gradle throw error "Circular dependency". Không thể build project có circular dependency vì không xác định được thứ tự build đúng.

JSON / YAML parser tree walk: Sau khi parse xong, cây AST được duyệt bằng DFS. Preorder cho serialize (ghi parent rồi children), postorder cho evaluate (tính value của 2 node con trước khi kết hợp tại node cha). Ví dụ: expression (a + b) * c là cây với * ở root, + ở left child — postorder evaluate tính a + b trước.

File system find / ls -R: DFS preorder tự nhiên — thư mục cha xuất hiện trước các file và thư mục con. find . -name "*.java" duyệt toàn bộ cây thư mục theo DFS, in path khi mỗi node được enter (preorder).

Browser call stack: Mỗi lần JavaScript gọi một function, engine push frame lên call stack, pop khi return. Call stack inherently là DFS — đi sâu vào call chain, pop dần khi return. Stack trace bạn thấy trong DevTools là snapshot của DFS traversal đang diễn ra tại moment đó.

10. Deep Dive

11. Tóm tắt

• DFS đi sâu theo từng nhánh trước khi quay lại — LIFO mechanic qua call stack hoặc explicit Stack.
• Recursive DFS ngắn gọn nhưng risk StackOverflow với graph sâu O(V); iterative DFS dùng Stack trên heap, an toàn hơn.
• Preorder: process đỉnh khi enter — dùng cho serialize, copy tree, file system traversal.
• Postorder: process đỉnh khi exit (sau tất cả children) — dùng cho delete tree, evaluate expression, dependency resolution.
• Cycle detection directed: white/gray/black coloring. GRAY = đang trên call stack = back-edge = cycle.
• Cycle detection undirected: boolean visited + track parent. Cạnh về đỉnh đã visited mà không phải parent = cycle.
• Connected components: DFS từ mỗi unvisited đỉnh = một component. O(V + E) tổng cộng.
• Reverse postorder của DFS trên DAG = topological sort (bài 04-topological-sort).

12. Tự kiểm tra

Bài tiếp theo: Topological sort — Kahn vs DFS-based