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 đứng trước v, nghĩa là mọi dependency đều được tôn trọng. Có hai thuật toán: Kahn (BFS, dùng in-degree, tức số cạnh đi vào một đỉnh) và DFS reverse postorder. Bẫy lớn nhất: không kiểm tra order.size() == n sau khi Kahn kết thúc. Nếu có cycle, thuật toán lặng lẽ trả về thứ tự thiếu đỉnh, và nơi dùng thứ tự đó sẽ build thiếu module mà không hay biết.

Mỗi lần bạn chạy mvn package, Maven phải biết module nào compile trước: common xong trước service, service xong trước api. Học đại học cũng vậy: Giải tích phải qua trước Xác suất thống kê, Cơ sở dữ liệu trước Cơ sở dữ liệu 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 ra thứ tự tính đúng. Còn nếu bạn tạo circular reference (ô A tham chiếu ô B, ô B lại tham chiếu ô A) thì Excel báo lỗi, vì thứ tự đó không tồn tại.

Tất cả đều là topological sort trên DAG. Bài này dạy 2 thuật toán topo sort (Kahn dựa trên BFS, DFS reverse postorder), cách phát hiện cycle, chuyện một DAG có nhiều thứ tự hợp lệ, và nơi các build tool dùng nó.

1. Hình dung: 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 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 mặc theo thứ tự nào cũng được, miễn là tôn trọng các ràng buộc.

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 thì khác: nếu một quy tắc nói "A mặc trước B" mà quy tắc khác nói "B mặc trước A", bạn không thể theo cả hai. Đó là circular dependency, không có thứ tự hợp lệ nào.

2. Định nghĩa

Topological order của một DAG là một thứ tự xếp hàng của tất cả đỉnh, sao cho với mọi cạnh có hướng u → v, đỉnh u đứng trước v.

Ba điều cần nhớ:

• Yêu cầu: graph phải là DAG (Directed Acyclic Graph). Có cycle thì không tồn tại topological order hợp lệ. Maven reactor dừng với lỗi cyclic reference, Gradle báo lỗi khi task phụ thuộc vòng, Excel cảnh báo circular reference.
• Nhiều thứ tự hợp lệ: thường có nhiều topological order hợp lệ chứ không chỉ một, và số lượng có thể tăng theo hàm mũ.
• DAG luôn có ít nhất một đỉnh với in-degree 0 (không phụ thuộc vào ai), và đó là điểm xuất phát của mọi thuật toán topo sort.

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ể đổi chỗ cho nhau vì không có cạnh nối 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)

Phát hiện cycle: nếu order.size() != V thì một số đỉnh có in-degree mãi dương (do cycle) nên 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. Bản trace dưới đây theo dõi hai biến inDegree và Queue qua từng bước, đúng kiểu bảng trace đã học ở khoá Nhập môn lập trình.

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 đứng trước v.

Thử ngẫmorder.size() == V là cách Kahn tự phát hiện cycle, không cần thêm bước riêng. Thêm cạnh 5→0 vào DAG này để tạo cycle, order dừng lại ở size bao nhiêu?

4. Algorithm 2 — DFS reverse postorder

Topo sort bằng DFS dựa trên điều đã học ở bài DFS: reverse postorder của DFS trên DAG chính là 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)

Vì sao đúng: postOrderStack.push(v) chạy sau khi đệ quy xong mọi đỉnh con cháu của v. Nghĩa là mọi đỉnh nằm phía sau v đã được push trước v. Khi pop từ stack (LIFO), v ra trước chúng, tức v đứng trước các đỉnh mà nó trỏ tới. Đó chính là topological order.

Phát hiện cycle: onStack[u] = true nghĩa là u đang là tổ tiên trên đường DFS 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.

Valid topological orders:

• [A, B, C, D]: hợp lệ vì A trước C, B trước C và D, C trước D.
• [B, A, C, D]: hợp lệ, A và B đổi chỗ được vì không có cạnh nối giữa chúng.

KHÔNG hợp lệ: [A, C, B, D], vì B phải trước C (B→C) mà ở đây B đứng sau C.

Có bao nhiêu thứ tự hợp lệ? Tuỳ cấu trúc DAG. Ví dụ trên chỉ có 2. Với DAG mà các đỉnh hoàn toàn độc lập (không có cạnh), mọi hoán vị đều hợp lệ, tức V! thứ tự.

Topo order nhỏ nhất theo thứ tự từ điển: thay Queue bằng MinHeap trong Kahn, luôn lấy ra đỉnh nhỏ nhất trong số các đỉnh có in-degree 0. Time là O(V log V + E) thay vì 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 log V + E) Space: O(V)

Thử ngẫmđổi Queue thành MinHeap trong Kahn làm độ phức tạp tăng từ O(V+E) lên O(V log V + E) để đổi lấy thứ tự từ điển. Nếu bài toán chỉ cần một thứ tự hợp lệ bất kỳ, đánh đổi này có đáng không?

7. Bẫy tổng hợp

Bẫy 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

Bẫy 2: Nhầm chiều cạnh

Trong dependency graph, nếu bạn quy ước cạnh u → v là "u phụ thuộc vào v" (Maven: artifact A depends on B thì B phải build trước A), thì khi thêm cạnh vào adjacency list rất dễ nhầm chiều, và kết quả sẽ bị đảo ngược.

-- 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)

Hãy thử với một ví dụ nhỏ trước khi đưa vào hệ thống: dựng graph 2 đỉnh, giải tay ra thứ tự mong đợi (thói quen ở Làm tay trước khi làm máy), rồi so với kết quả chạy.

Bẫy 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 đi được cả hai chiều, nên không xác định được đỉnh nào "trước" đỉnh nào.

Nếu bạn dựng adjacency list undirected rồi chạy Kahn, kết quả vô nghĩa. Nếu chạy bản DFS, onStack sẽ báo cycle ngay (vì mọi cạnh undirected xuất hiện ở cả hai chiều, nên quay về parent bị tính nhầm là "back-edge").

Hãy kiểm tra graph là directed trước khi topo sort. Với undirected graph, dùng BFS/DFS để tìm connected component thay thế.

8. Dùng ở đâu trong thực tế

Thứ tự build của Maven: với dự án nhiều module, Maven dựng đồ thị phụ thuộc giữa các module trong reactor rồi sắp xếp topo để ra thứ tự build (bạn thấy nó ở dòng "Reactor Build Order" đầu mỗi lần chạy). Nếu có cycle (A depends on B, B depends on A), Maven dừng với lỗi bắt đầu bằng "The projects in the reactor contain a cyclic reference". Phải phá cycle mới build được, thường bằng cách tách code dùng chung ra một module riêng.

Make / Bazel / Gradle task graph: Các target của Makefile và task của Gradle là DAG. Build tool dựa trên thứ tự topo để biết task nào đã đủ điều kiện chạy; các task không phụ thuộc nhau có thể chạy song song mà không vi phạm dependency.

Tính lại công thức trong Excel: Excel giữ đồ thị phụ thuộc giữa các ô và tính lại sao cho ô nào dùng giá trị của ô khác thì được tính sau. Circular reference (A1 = B1 + 1, B1 = A1 + 1) làm đồ thị có cycle, nên Excel cảnh báo (trừ khi bạn chủ động bật tính lặp).

9. Đào sâu

10. Tóm tắt

• Topological sort chỉ áp dụng cho DAG; sắp xếp sao cho mọi cạnh u → v có u xuất hiện trước v.
• Kahn (BFS queue): tính in-degree, bóc đỉnh bậc 0 và trừ dần bậc hàng xóm. Luôn kiểm tra order.size() == V để phát hiện cycle.
• DFS reverse postorder: push đỉnh vào stack khi duyệt xong nhánh con cháu; phát hiện cycle bằng cờ onStack.
• Kahn hợp hơn khi cần thứ tự từ điển (dùng MinHeap) hoặc đồ thị sâu; DFS hợp hơn khi cần triển khai ngắn gọn.
• Nhầm chiều cạnh là bug phổ biến nhất: u phụ thuộc v thì cạnh định hướng phải là v → u.

11. Tự kiểm tra

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