Topological sort — Kahn (BFS-based) vs DFS-based, build order DAG

Mỗi khi bạn chạy mvn package, Maven phải biết module nào compile trước — common phải xong trước service, service trước api. Khi bạn học một chương trình đại học, môn Giải tích phải qua trước Xác suất thống kê, Cơ sở dữ liệu trước Phân tán. Khi Excel tính lại một sheet có hàng nghìn công thức phụ thuộc nhau, nó phải tìm thứ tự tính đúng. Khi bạn tạo circular reference trong Excel, nó báo lỗi #REF! — vì thứ tự đó không tồn tại.

Tất cả là topological sort trên DAG. Bài này dạy 2 algorithm topo sort (Kahn BFS-based, DFS reverse postorder), detect cycle, multiple valid order, và pattern Maven/Gradle/npm/Excel/job scheduler dùng.

1. Analogy — Mặc đồ buổi sáng

Mỗi sáng bạn phải mặc nhiều thứ, và chúng có thứ tự phụ thuộc: tất phải mặc trước giày, áo trong trước áo ngoài, quần trước thắt lưng. Nhưng không có "thứ tự duy nhất" — bạn có thể mặc theo nhiều thứ tự hợp lệ khác nhau, chỉ cần tôn trọng dependency.

Ví dụ hai thứ tự đều hợp lệ:

• tất → quần → giày → áo trong → áo ngoài
• áo trong → quần → tất → áo ngoài → giày

Cycle: nếu quy tắc nói "A phải mặc trước B" và đồng thời "B phải mặc trước A" — không thể tuân theo cả hai. Đây là circular dependency, không có valid order.

2. Định nghĩa

Topological order của một DAG là một linear ordering của tất cả vertices sao cho với mọi directed edge u → v, vertex u xuất hiện trước v trong ordering đó.

Ba điều cần nhớ:

• Yêu cầu: graph phải là DAG (Directed Acyclic Graph). Có cycle → không tồn tại valid topological order. Maven throw CircularDependencyException, Gradle throw build error, Excel báo #REF!.
• Multiple valid orders: thường có nhiều topological order hợp lệ, không phải một. Số lượng valid order có thể là exponential.
• DAG luôn có ít nhất một vertex với in-degree 0 (không có dependency) — đây là điểm khởi đầu của mọi topo sort algorithm.

3. Algorithm 1 — Kahn (BFS-based)

3.1 Idea

1. Tính in-degree của mỗi vertex (số edge đến nó).
2. Tất cả vertex có in-degree = 0 không có dependency — đặt vào queue.
3. Poll một vertex ra, thêm vào result order.
4. "Remove" vertex đó khỏi graph: giảm in-degree của mỗi neighbor đi 1.
5. Neighbor nào vừa xuống in-degree = 0 thì enqueue.
6. Lặp đến khi queue rỗng.
7. Nếu result chứa ít hơn V vertices → có cycle (một số vertex chưa bao giờ có in-degree = 0).

import java.util.*;

public static List<Integer> topoKahn(List<List<Integer>> adj) {
    int n = adj.size();
    int[] inDegree = new int[n];
    for (int u = 0; u < n; u++) {
        for (int v : adj.get(u)) inDegree[v]++;
    }

    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) queue.offer(i);
    }

    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int v = queue.poll();
        order.add(v);
        for (int u : adj.get(v)) {
            if (--inDegree[u] == 0) queue.offer(u);
        }
    }

    if (order.size() != n) {
        throw new IllegalStateException("Graph has cycle");
    }
    return order;
}

Complexity:

• Time: O(V + E) — mỗi vertex enqueue đúng một lần, mỗi edge xử lý đúng một lần.
• Space: O(V) — queue + in-degree array.
• Cycle detection: nếu order.size() != n, một số vertex có in-degree mãi dương (do cycle) — không bao giờ vào queue.

3.2 Trace ví dụ

DAG 6 vertex: 0→2, 1→2, 1→3, 2→4, 3→4, 4→5.

In-degree ban dau: [0, 0, 2, 1, 2, 1]
Queue init: [0, 1]   (in-degree = 0)

Buoc 1: poll 0, order=[0]. Neighbor 2: inDegree[2]=2-1=1. Queue: [1]
Buoc 2: poll 1, order=[0,1]. Neighbor 2: inDegree[2]=1-1=0 -> enqueue. Neighbor 3: inDegree[3]=1-1=0 -> enqueue. Queue: [2, 3]
Buoc 3: poll 2, order=[0,1,2]. Neighbor 4: inDegree[4]=2-1=1. Queue: [3]
Buoc 4: poll 3, order=[0,1,2,3]. Neighbor 4: inDegree[4]=1-1=0 -> enqueue. Queue: [4]
Buoc 5: poll 4, order=[0,1,2,3,4]. Neighbor 5: inDegree[5]=1-1=0 -> enqueue. Queue: [5]
Buoc 6: poll 5, order=[0,1,2,3,4,5]. Queue: []

order.size()=6 == n=6 -> no cycle

Kết quả: [0, 1, 2, 3, 4, 5] — hợp lệ vì mọi edge u → v đều có u trước v.

4. Algorithm 2 — DFS reverse postorder

DFS-based topo sort dựa trên một insight từ bài trước: reverse postorder của DFS trên DAG = topological order.

public static List<Integer> topoDFS(List<List<Integer>> adj) {
    int n = adj.size();
    boolean[] visited = new boolean[n];
    boolean[] onStack = new boolean[n];
    Deque<Integer> postOrder = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        if (!visited[i]) dfsHelper(adj, i, visited, onStack, postOrder);
    }

    List<Integer> result = new ArrayList<>();
    while (!postOrder.isEmpty()) result.add(postOrder.pop());
    return result;
}

private static void dfsHelper(List<List<Integer>> adj, int v,
                               boolean[] visited, boolean[] onStack,
                               Deque<Integer> postOrder) {
    visited[v] = true;
    onStack[v] = true;
    for (int u : adj.get(v)) {
        if (onStack[u]) throw new IllegalStateException("Cycle detected");
        if (!visited[u]) dfsHelper(adj, u, visited, onStack, postOrder);
    }
    onStack[v] = false;
    postOrder.push(v);  // push AFTER all descendants done -- reverse postorder via stack
}

Insight: postOrder.push(v) được gọi sau khi đệ quy qua tất cả descendants của v. Nghĩa là mọi vertex phụ thuộc vào v đã được push trước v. Khi pop từ stack (LIFO), v ra trước — v xuất hiện trước dependencies của nó. Đây chính là topological order.

Cycle detection: onStack[u] == true nghĩa là u đang là ancestor trên DFS path hiện tại (màu GRAY trong bài DFS). Edge từ v đến GRAY vertex = back-edge = cycle (cross-link lesson 03, section 5).

Complexity:

• Time: O(V + E).
• Space: O(V) — recursion stack + visited arrays.

5. Kahn vs DFS — bảng so sánh

6. Multiple valid orders

DAG: A→C, B→C, B→D, C→D.

A --> C --> D
      ^     ^
B ----+-----+

Valid topological orders:

• [A, B, C, D] — hợp lệ: A trước C, B trước C và D, C trước D.
• [B, A, C, D] — hợp lệ: thứ tự A và B có thể hoán đổi vì không có edge giữa chúng.

KHÔNG hợp lệ: [A, C, B, D] — B phải trước C (B→C), nhưng trong order này B ở sau C.

Bao nhiêu valid orders? Phụ thuộc vào cấu trúc DAG. Trong ví dụ trên chỉ có 2. Với DAG hoàn toàn độc lập (không có edge), mọi permutation đều hợp lệ — V! orders.

Lexicographically smallest topo order: thay Queue<Integer> bằng PriorityQueue<Integer> trong Kahn — luôn poll vertex nhỏ nhất in-degree-0 trước. Với ví dụ trên: PQ poll A (nhỏ hơn B) → [A, B, C, D]. Time: O((V + E) log V) thay O(V + E).

// Lexicographically smallest: replace Queue with PriorityQueue
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
    if (inDegree[i] == 0) pq.offer(i);
}
// rest of Kahn algorithm unchanged -- pq.poll() always returns min

7. Pitfall tổng hợp

Pitfall 1 — Quên kiểm tra cycle sau khi chạy Kahn

// BUG: returns partial order if graph has a cycle
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
    int v = queue.poll();
    order.add(v);
    for (int u : adj.get(v)) {
        if (--inDegree[u] == 0) queue.offer(u);
    }
}
return order;  // could be [0, 1] for a 4-vertex graph with cycle 2->3->2

Nếu có cycle, một số vertex có in-degree mãi dương và không bao giờ vào queue. Algorithm trả về partial order — consumer dùng order đó để build/install sẽ bỏ qua một số module, dẫn đến corrupted state.

// CORRECT: always verify
if (order.size() != n) {
    throw new IllegalStateException("Graph has cycle -- no valid topo order");
}
return order;

Pitfall 2 — Nhầm chiều edge

Edge u → v trong dependency graph nghĩa là "u phụ thuộc vào v" (Maven: artifact A depends on B → B phải build trước A). Khi thêm edge vào adjacency list, nhầm chiều sẽ cho reverse order.

// BUG: "A depends on B" but added as A -> B meaning "A before B"
// When it should be B -> A meaning "B before A"
adj.get(a).add(b);   // wrong direction

// CORRECT: B must come before A
adj.get(b).add(a);

Test với 1 ví dụ nhỏ trước khi integrate: build graph 2 vertex, verify topo order đúng chiều.

Pitfall 3 — Chạy topo sort trên undirected graph

Topological sort chỉ có nghĩa với directed graph. Undirected graph không có khái niệm "thứ tự" vì mọi edge là hai chiều — không xác định được vertex nào "trước" vertex nào.

Nếu bạn build undirected adjacency list rồi chạy Kahn, kết quả là vô nghĩa. Nếu chạy DFS-based, onStack sẽ detect cycle ngay lập tức (vì mọi undirected edge xuất hiện cả hai chiều — trở về parent là "back-edge" giả).

Luôn verify graph là directed trước khi topo sort. Với undirected graph, dùng BFS/DFS detect component thay thế.

8. Applied to tech

Maven mvn dependency:tree build order: Maven xây DAG từ <dependency> trong pom.xml. Topo sort DAG đó cho thứ tự compile artifact. Nếu có cycle (A depends on B, B depends on A), Maven throw AbstractArtifactResolutionException với thông báo circular dependency. Không thể build project cho đến khi cycle được phá vỡ (thường bằng cách extract shared code ra module riêng).

npm package-lock.json install order: npm đọc package-lock.json, xây dependency DAG, topo sort trước khi flatten vào node_modules. Khi topo sort xong, npm install các package không có dependency trước (leaf node trong DAG), rồi mới install package phụ thuộc vào chúng. Circular dependency trong npm (A → B → A) được xử lý đặc biệt bằng symlink — nhưng vẫn là edge case đáng tránh.

Make / Bazel / Gradle task graph: Makefile targets và Gradle tasks là DAG. Build tool chạy topo sort, sau đó execute task theo level song song — tất cả task ở cùng level (không phụ thuộc nhau) chạy song song. Topo sort cho phép tối đa hóa parallelism mà không vi phạm dependency.

Excel formula recalculation: Excel duy trì DAG của công thức. Khi bạn sửa ô A1, Excel chạy topo sort để tìm thứ tự tính lại các ô phụ thuộc vào A1. Circular reference (A1 = B1 + 1, B1 = A1 + 1) → DAG có cycle → Excel không thể tính → báo #REF! hoặc giá trị lỗi.

Database migration runner (Flyway, Liquibase): migration scripts có thể có dependency (V2 cần V1 apply trước). Flyway track applied migrations và chạy pending scripts theo version order — một dạng topo sort đơn giản trên chain. Liquibase cho phép explicit dependency giữa changeset — phức tạp hơn, topo sort thực sự.

9. Deep Dive

10. Tóm tắt

• Topological sort sắp xếp vertices của DAG sao cho mọi edge u → v có u trước v. Chỉ áp dụng cho DAG — có cycle thì không tồn tại valid order.
• Kahn (BFS-based): tính in-degree, queue tất cả vertex có in-degree 0, poll và decrement neighbor. Cycle detection bằng order.size() != n. Iterative, không risk stack overflow.
• DFS reverse postorder: push vertex vào stack sau khi xử lý xong toàn bộ descendants. Pop stack cho topological order. Cycle detection bằng onStack array (gray coloring).
• Kahn tốt hơn khi cần lexicographic order (dùng PriorityQueue) hoặc streaming graph. DFS tốt hơn khi graph đã build sẵn và muốn code ngắn.
• Multiple valid orders tồn tại khi có vertex không có dependency thứ tự với nhau. Lexicographic smallest = Kahn với PriorityQueue, O((V + E) log V).
• Luôn verify order.size() == n sau Kahn — partial order từ cycle là silent bug nguy hiểm.
• Nhầm chiều edge là bug phổ biến nhất: u depends on v → edge v → u (v trước u), không phải u → v.

11. Tự kiểm tra

Bài tiếp theo: Dijkstra — relaxation, priority queue