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

TL;DR: Topological sort sắp xếp các đỉnh của DAG sao cho với mọi cạnh u → v, đỉnh u xuất hiện trước v — tức là mọi dependency được thỏa mãn. Có hai algorithm: Kahn (BFS, dùng in-degree) và DFS reverse postorder. Pitfall lớn nhất: không kiểm tra order.size() == n sau khi Kahn kết thúc — nếu có cycle, algorithm im lặng trả về partial order, consumer dùng order đó sẽ build thiếu module mà không biết.

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ả đỉnh sao cho với mọi directed edge u → v, đỉnh 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 đỉnh với in-degree 0 (không có dependency) — đây là điểm khởi đầu của mọi topo sort algorithm.

graph LR
    A["Đỉnh A\nin-degree=0"] --> C["Đỉnh C\nin-degree=2"]
    B["Đỉnh B\nin-degree=0"] --> C
    B --> D["Đỉnh D\nin-degree=1"]
    C --> E["Đỉnh E\nin-degree=2"]
    D --> E

Với DAG trên, các thứ tự hợp lệ bao gồm [A, B, C, D, E] và [B, A, C, D, E] và [B, A, D, C, E] — A và B có thể hoán đổi vì không có cạnh giữa chúng.

3. Algorithm 1 — Kahn (BFS-based)

3.1 Idea

Kahn(G):
    -- Bước 1: tính in-degree của mỗi đỉnh
    inDegree[v] <- 0 cho mọi v
    for each đỉnh u trong G:
        for each đỉnh v kề u:
            inDegree[v] <- inDegree[v] + 1

    -- Bước 2: tất cả đỉnh không có dependency vào queue
    Q <- Queue rỗng
    for each đỉnh v trong G:
        if inDegree[v] = 0:
            Q.enqueue(v)

    order <- []
    while Q không rỗng:
        v <- Q.dequeue()
        order.append(v)

        -- "Xóa" v khỏi graph: giảm in-degree của hàng xóm
        for each đỉnh u kề v:
            inDegree[u] <- inDegree[u] - 1
            if inDegree[u] = 0:
                Q.enqueue(u)       -- u không còn dependency nào chưa xử lý

    -- Kiểm tra cycle: nếu chưa xử lý hết đỉnh, có cycle
    if order.size() != V:
        báo lỗi "Graph có cycle — không có valid topo order"

    return order

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

Cycle detection: nếu order.size() != V, một số đỉnh có in-degree mãi dương (do cycle) — không bao giờ vào queue.

3.2 Trace ví dụ

DAG 6 đỉnh: 0→2, 1→2, 1→3, 2→4, 3→4, 4→5.

In-degree ban đầu: [0, 0, 2, 1, 2, 1]
Queue khởi tạo: [0, 1]   (in-degree = 0)

Bước 1: lấy 0, order=[0]. Hàng xóm 2: inDegree[2]=2-1=1. Queue: [1]
Bước 2: lấy 1, order=[0,1]. Hàng xóm 2: inDegree[2]=1-1=0 -> enqueue. Hàng xóm 3: inDegree[3]=0 -> enqueue. Queue: [2, 3]
Bước 3: lấy 2, order=[0,1,2]. Hàng xóm 4: inDegree[4]=2-1=1. Queue: [3]
Bước 4: lấy 3, order=[0,1,2,3]. Hàng xóm 4: inDegree[4]=0 -> enqueue. Queue: [4]
Bước 5: lấy 4, order=[0,1,2,3,4]. Hàng xóm 5: inDegree[5]=0 -> enqueue. Queue: [5]
Bước 6: lấy 5, order=[0,1,2,3,4,5]. Queue: []

order.size()=6 == V=6 -> không có cycle

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

4. Algorithm 2 — DFS reverse postorder

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

topoDFS(G):
    visited[v] <- false cho mọi v
    onStack[v] <- false cho mọi v    -- phát hiện cycle (tương đương GRAY)
    postOrderStack <- Stack rỗng

    for each đỉnh v trong G:
        if not visited[v]:
            dfsHelper(G, v, visited, onStack, postOrderStack)

    -- Pop stack cho topological order
    result <- []
    while postOrderStack không rỗng:
        result.append(postOrderStack.pop())
    return result

dfsHelper(G, v, visited, onStack, postOrderStack):
    visited[v] <- true
    onStack[v] <- true               -- đánh dấu đang trên call stack

    for each đỉnh u kề v:
        if onStack[u]: báo lỗi "Phát hiện cycle"   -- back-edge
        if not visited[u]:
            dfsHelper(G, u, visited, onStack, postOrderStack)

    onStack[v] <- false
    postOrderStack.push(v)           -- push SAU KHI tất cả con xong

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

Insight: postOrderStack.push(v) được gọi sau khi đệ quy qua tất cả descendants của v. Nghĩa là mọi đỉnh 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, section 5).

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

6. Multiple valid orders

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

graph LR
    A["A"] --> C["C"]
    B["B"] --> C
    B --> D["D"]
    C --> D

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ó cạnh 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ó cạnh), mọi permutation đều hợp lệ — V! orders.

Lexicographically smallest topo order: thay Queue bằng MinHeap trong Kahn — luôn poll đỉnh nhỏ nhất in-degree-0 trước. Time: O((V + E) log V) thay O(V + E).

-- Thay Queue bằng MinHeap để có lexicographic order
H <- MinHeap rỗng
for each đỉnh v với inDegree[v] = 0:
    H.push(v)

while H không rỗng:
    v <- H.pop()                   -- lấy đỉnh nhỏ nhất
    order.append(v)
    for each đỉnh u kề v:
        inDegree[u] <- inDegree[u] - 1
        if inDegree[u] = 0:
            H.push(u)

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

7. Pitfall tổng hợp

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

-- BUG: trả về partial order khi graph có cycle
order <- []
while Q không rỗng:
    v <- Q.dequeue()
    order.append(v)
    for each u kề v:
        inDegree[u] <- inDegree[u] - 1
        if inDegree[u] = 0: Q.enqueue(u)
return order   -- có thể là [0, 1] cho graph 4 đỉnh có cycle 2->3->2
-- Consumer dùng order đó để build: bỏ qua module 2 và 3 -> corrupted state

-- ĐÚNG: luôn kiểm tra sau khi Kahn kết thúc
if order.size() != V:
    báo lỗi "Graph có cycle -- không có valid topo order"
return order

Pitfall 2 — Nhầm chiều cạnh

Cạnh 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 cạnh vào adjacency list, nhầm chiều sẽ cho reverse order.

-- BUG: "A phụ thuộc B" nhưng thêm cạnh A -> B nghĩa là "A trước B"
-- Đúng phải là B -> A nghĩa là "B trước A"
adj[a].append(b)    -- sai chiều

-- ĐÚNG: B phải đến trước A
adj[b].append(a)

Test với 1 ví dụ nhỏ trước khi integrate: build graph 2 đỉnh, 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 cạnh là hai chiều — không xác định được đỉnh nào "trước" đỉnh 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 đỉnh của DAG sao cho mọi cạnh 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ả đỉnh có in-degree 0, poll và decrement hàng xóm. Cycle detection bằng order.size() != V. Iterative, không risk stack overflow.
• DFS reverse postorder: push đỉnh 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 MinHeap) 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ó đỉnh không có dependency thứ tự với nhau. Lexicographic smallest = Kahn với MinHeap, O((V + E) log V).
• Luôn verify order.size() == V sau Kahn — partial order từ cycle là silent bug nguy hiểm.
• Nhầm chiều cạnh là bug phổ biến nhất: u depends on v → cạnh 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