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

BFS lan sóng theo từng level — nó biết "vertex 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

public class DFS {

    // Entry point: DFS from a single start vertex.
    public static void dfs(List<List<Integer>> adj, int start) {
        boolean[] visited = new boolean[adj.size()];
        dfsHelper(adj, start, visited);
    }

    private static void dfsHelper(List<List<Integer>> adj, int v, boolean[] visited) {
        if (visited[v]) return;
        visited[v] = true;

        System.out.println("preorder: " + v);   // process BEFORE recursing children

        for (int u : adj.get(v)) {
            dfsHelper(adj, u, visited);
        }

        System.out.println("postorder: " + v);  // process AFTER all children done
    }
}

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

Call tree:
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

preorder order:  0, 1, 3, 4, 2
postorder order: 3, 4, 1, 2, 0

Complexity:

• Time: O(V + E) — mỗi vertex visit đúng một lần, mỗi edge kiểm tra một lần (hoặc hai lần với undirected).
• Space: O(V) — call stack sâu tối đa V frame (worst case: chain graph).

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 vertex sẽ crash JVM (xem Module 1 lesson 02 và Module 2 lesson 03). Giải pháp: dùng Deque trên heap làm explicit stack.

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

    while (!stack.isEmpty()) {
        int v = stack.pop();
        if (visited[v]) continue;
        visited[v] = true;
        System.out.println(v);

        // Push neighbors in REVERSE order to get same traversal as recursive
        List<Integer> neighbors = adj.get(v);
        for (int i = neighbors.size() - 1; i >= 0; i--) {
            int u = neighbors.get(i);
            if (!visited[u]) stack.push(u);
        }
    }
}

Tại sao push reverse? Recursive DFS xử lý neighbor theo thứ tự tự nhiên (index 0, 1, 2...). Stack là LIFO — nếu push theo thứ tự tự nhiên, neighbor cuối sẽ được pop ra trước. Push reverse → neighbor đầ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.

private static void dfsBoth(List<List<Integer>> adj, int v, boolean[] visited) {
    visited[v] = true;
    processPre(v);               // preorder: ngay khi enter vertex

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

    processPost(v);              // postorder: sau khi ALL children done
}

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 tiếp theo sẽ phân tích chi tiết.

5. Cycle detection — white/gray/black coloring

Cách đơn giản nhất để detect 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 — vertex 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ừ vertex v gặp neighbor 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 (edge vừa xét). Đây là back-edge → cycle.

enum Color { WHITE, GRAY, BLACK }

public static boolean hasCycle(List<List<Integer>> adj) {
    int n = adj.size();
    Color[] color = new Color[n];
    Arrays.fill(color, Color.WHITE);

    for (int i = 0; i < n; i++) {
        if (color[i] == Color.WHITE) {
            if (dfsCheck(adj, i, color)) return true;
        }
    }
    return false;
}

private static boolean dfsCheck(List<List<Integer>> adj, int v, Color[] color) {
    color[v] = Color.GRAY;                   // entering: on the stack now

    for (int u : adj.get(v)) {
        if (color[u] == Color.GRAY) return true;   // back-edge -> cycle
        if (color[u] == Color.WHITE && dfsCheck(adj, u, color)) return true;
    }

    color[v] = Color.BLACK;                  // leaving: fully processed
    return false;
}

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". Nếu chỉ dùng boolean:

// BUG on directed graph -- false positive cycle detection
// Graph: A -> B, A -> C, B -> D, C -> D
// DFS from A: A->B->D (mark D visited), backtrack to A->C->D
// D is visited but we came here from a DIFFERENT path -- NOT a cycle
// With boolean: we'd skip D (already visited) -- fine, no cycle detected
// BUT: if D -> A existed, we need GRAY to catch it as a back-edge
// boolean "visited=true" for D doesn't tell us if D is currently on stack

GRAY nghĩa là đang trên call stack ngay lúc này. BLACK nghĩa là đã xong, không còn trên stack. Chỉ GRAY mới là back-edge và cycle.

Undirected graph: Mọi edge trở lại parent trong DFS đều là back-edge (vì undirected graph không có chiều). Nhưng đây không phải cycle — cùng một cạnh, nhìn từ hai phía. Cần exclude parent:

private static boolean dfsCheckUndirected(List<List<Integer>> adj,
                                           int v, int parent, boolean[] visited) {
    visited[v] = true;
    for (int u : adj.get(v)) {
        if (!visited[u]) {
            if (dfsCheckUndirected(adj, u, v, visited)) return true;
        } else if (u != parent) {
            return true;  // back-edge to non-parent -> cycle
        }
    }
    return false;
}

6. Connected components — undirected graph

Đếm số connected component trong undirected graph: mỗi lần DFS từ một vertex chưa thăm sẽ visit đúng một component (tất cả vertex có thể đến được từ đó). Sau khi DFS xong, nếu còn vertex trắng, đó là component mới.

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

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfsHelper(adj, i, visited);   // visit all reachable from i
            count++;                      // one new component found
        }
    }
    return count;
}

Nếu graph có K component, vòng for ngoài sẽ trigger DFS đúng K lần — mỗi lần mark toàn bộ component đó rồi increment counter.

Complexity: O(V + E) — tổng cộng mỗi vertex và edge 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

Chain graph (0→1→2→...→N-1) với N = 1.000.000: recursive DFS depth = N frames. JVM với -Xss 512k crash sau khoảng 10.000–20.000 frame.

// BAD: recursive DFS on chain graph with 1M vertices
// JVM crashes with StackOverflowError around depth 10k-20k
dfsHelper(adj, 0, visited);

// GOOD: iterative DFS -- stack lives on heap, not thread stack
dfsIterative(adj, 0);  // handles 1M+ depth safely

Nếu buộc phải dùng recursive, có thể tăng -Xss cho thread cụ thể: new Thread(null, runnable, "dfs-thread", 64 * 1024 * 1024) — nhưng đây là workaround, không phải giải pháp. Xem thêm Module 1 lesson 02.

Pitfall 2 — Cycle detection sai trên undirected graph

Trên undirected graph, mọi edge (u, v) xuất hiện hai lần trong adjacency list. Khi DFS từ u đến v, và từ v nhìn lại thấy u đã visited — đây không phải cycle:

// BUG: no parent tracking -- false positive on undirected graph
private static boolean buggyCheck(List<List<Integer>> adj, int v, boolean[] vis) {
    vis[v] = true;
    for (int u : adj.get(v)) {
        if (vis[u]) return true;   // BUG: u could just be the parent
    }
    return false;
}

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: check visited AFTER entering dfsHelper, not before recursing
private static void buggyDfs(List<List<Integer>> adj, int v, boolean[] visited) {
    visited[v] = true;
    for (int u : adj.get(v)) {
        buggyDfs(adj, u, visited); // no check -- can enter u multiple times
    }
}

Với graph có nhiều đường tới cùng một vertex, buggyDfs sẽ recurse vào u nhiều lần — exponential time. Fix: kiểm tra visited[u] trước khi gọi đệ quy (hoặc check visited[v] ngay đầu hàm, như code trong section 2).

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 node đí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 5.

Articulation points và bridges: một vertex là articulation point nếu xóa nó làm graph bị ngắt kết nối. Một edge 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, JVM (hay V8 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 Deque.
• Recursive DFS ngắn gọn nhưng risk StackOverflowError với graph sâu O(V); iterative DFS dùng Deque trên heap, an toàn hơn.
• Preorder: process vertex khi enter — dùng cho serialize, copy tree, file system traversal.
• Postorder: process vertex 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. Edge về node visited mà không phải parent = cycle.
• Connected components: DFS từ mỗi unvisited vertex = một component. O(V + E) tổng cộng.
• Reverse postorder của DFS trên DAG = topological sort (bài tiếp theo).

12. Tự kiểm tra

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