Topological Sort — Sắp xếp phụ thuộc

Mỗi lần bạn chạy npm install, gradle build, hay make, có một thuật toán âm thầm quyết định thứ tự xử lý hàng trăm package. Cài react-dom trước react? Build lỗi. Compile main.cpp trước utils.o? Linker báo undefined symbol. Thuật toán đó là Topological Sort — sắp xếp tuyến tính các đỉnh của đồ thị có hướng không chu trình (DAG) sao cho mọi cạnh u → v đều có u đứng trước v.

Topological Sort không chỉ giải quyết bài toán lý thuyết. Nó là xương sống của mọi hệ thống phụ thuộc: từ CI/CD pipeline, course prerequisite planning, đến spreadsheet cell evaluation. Hiểu rõ hai cách tiếp cận — Kahn (BFS) và DFS — cùng khả năng phát hiện chu trình sẽ cho bạn công cụ giải quyết toàn bộ lớp bài toán dependency ordering.

Bức tranh tư duy

Hình dung buổi sáng bạn mặc đồ đi làm. Bạn không thể đi giày trước khi mang tất. Không thể mặc áo khoác trước khi mặc áo sơ mi. Mỗi bước phụ thuộc vào bước trước đó — đó chính là quan hệ phụ thuộc trong DAG.

text

Quần lót → Quần dài → Thắt lưng → Áo khoác
Tất     → Giày
Áo lót  → Áo sơ mi → Cà vạt → Áo khoác

Một thứ tự hợp lệ:
  Quần lót → Tất → Áo lót → Quần dài → Áo sơ mi → Giày → Thắt lưng → Cà vạt → Áo khoác

Thứ tự hợp lệ khác:
  Áo lót → Quần lót → Tất → Áo sơ mi → Quần dài → Giày → Cà vạt → Thắt lưng → Áo khoác

Hai quy tắc vàng: (1) mỗi item chỉ được mặc sau các item nó phụ thuộc, và (2) có thể tồn tại nhiều thứ tự hợp lệ. Nếu bạn phát hiện một vòng phụ thuộc — tất cần giày, giày cần quần, quần cần tất — thì không tồn tại thứ tự hợp lệ nào. Đó là chu trình (cycle), và Topological Sort phải phát hiện được nó.

📌 Khi nào analogy bị phá vỡ

Mặc đồ là DAG nhỏ (~10 items). Trong production, dependency graph có thể lên đến hàng nghìn node (npm registry, Gradle modules). Lúc đó, hiệu năng O(V+E) và khả năng parallelism (nhiều task cùng level chạy song song) mới thực sự quan trọng.

Cốt lõi kỹ thuật

Kahn's Algorithm — BFS với in-degree

Ý tưởng: liên tục chọn đỉnh có in-degree = 0 (không phụ thuộc ai), xử lý nó, rồi giảm in-degree của các đỉnh kề. Nếu cuối cùng không xử lý hết tất cả đỉnh — đồ thị có chu trình.

C++PythonJavaGo

cpp

#include <vector>
#include <queue>
using namespace std;

vector<int> topoSortKahn(int V, vector<vector<int>>& adj) {
    vector<int> indeg(V, 0);
    for (int u = 0; u < V; u++)
        for (int v : adj[u]) indeg[v]++;

    queue<int> q;
    for (int i = 0; i < V; i++)
        if (indeg[i] == 0) q.push(i);

    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (--indeg[v] == 0) q.push(v);
        }
    }
    return order.size() == V ? order : vector<int>{};
}

python

from collections import deque

def topo_sort_kahn(V: int, adj: list[list[int]]) -> list[int]:
    indeg = [0] * V
    for u in range(V):
        for v in adj[u]:
            indeg[v] += 1

    q = deque(i for i in range(V) if indeg[i] == 0)
    order = []

    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    return order if len(order) == V else []

java

import java.util.*;

public class TopoSort {
    public static List<Integer> kahnSort(int V, List<List<Integer>> adj) {
        int[] indeg = new int[V];
        for (int u = 0; u < V; u++)
            for (int v : adj.get(u)) indeg[v]++;

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < V; i++)
            if (indeg[i] == 0) q.add(i);

        List<Integer> order = new ArrayList<>();
        while (!q.isEmpty()) {
            int u = q.poll();
            order.add(u);
            for (int v : adj.get(u))
                if (--indeg[v] == 0) q.add(v);
        }
        return order.size() == V ? order : Collections.emptyList();
    }
}

func topoSortKahn(V int, adj [][]int) []int {
    indeg := make([]int, V)
    for u := 0; u < V; u++ {
        for _, v := range adj[u] {
            indeg[v]++
        }
    }
    q := []int{}
    for i := 0; i < V; i++ {
        if indeg[i] == 0 {
            q = append(q, i)
        }
    }
    order := []int{}
    for len(q) > 0 {
        u := q[0]
        q = q[1:]
        order = append(order, u)
        for _, v := range adj[u] {
            indeg[v]--
            if indeg[v] == 0 {
                q = append(q, v)
            }
        }
    }
    if len(order) == V {
        return order
    }
    return nil
}

DFS-based Topological Sort

Ý tưởng: duyệt DFS từ mỗi đỉnh chưa visit. Khi hoàn thành DFS tại đỉnh u (tất cả con cháu đã xử lý xong), push u vào stack. Kết quả cuối cùng là reverse của stack. Phát hiện chu trình bằng trạng thái VISITING — nếu gặp lại đỉnh đang VISITING, tức tồn tại back edge.

C++PythonJavaGo

cpp

#include <vector>
#include <algorithm>
using namespace std;

enum State { UNVISITED, VISITING, VISITED };

bool dfs(int u, vector<vector<int>>& adj, vector<State>& state,
         vector<int>& order) {
    state[u] = VISITING;
    for (int v : adj[u]) {
        if (state[v] == VISITING) return false;
        if (state[v] == UNVISITED && !dfs(v, adj, state, order))
            return false;
    }
    state[u] = VISITED;
    order.push_back(u);
    return true;
}

vector<int> topoSortDFS(int V, vector<vector<int>>& adj) {
    vector<State> state(V, UNVISITED);
    vector<int> order;
    for (int i = 0; i < V; i++) {
        if (state[i] == UNVISITED && !dfs(i, adj, state, order))
            return {};
    }
    reverse(order.begin(), order.end());
    return order;
}

python

from enum import IntEnum

class State(IntEnum):
    UNVISITED = 0
    VISITING = 1
    VISITED = 2

def topo_sort_dfs(V: int, adj: list[list[int]]) -> list[int]:
    state = [State.UNVISITED] * V
    order: list[int] = []

    def dfs(u: int) -> bool:
        state[u] = State.VISITING
        for v in adj[u]:
            if state[v] == State.VISITING:
                return False
            if state[v] == State.UNVISITED and not dfs(v):
                return False
        state[u] = State.VISITED
        order.append(u)
        return True

    for i in range(V):
        if state[i] == State.UNVISITED and not dfs(i):
            return []

    return order[::-1]

java

import java.util.*;

public class TopoSortDFS {
    enum State { UNVISITED, VISITING, VISITED }

    public static List<Integer> sort(int V, List<List<Integer>> adj) {
        State[] state = new State[V];
        Arrays.fill(state, State.UNVISITED);
        List<Integer> order = new ArrayList<>();

        for (int i = 0; i < V; i++)
            if (state[i] == State.UNVISITED)
                if (!dfs(i, adj, state, order))
                    return Collections.emptyList();

        Collections.reverse(order);
        return order;
    }

    private static boolean dfs(int u, List<List<Integer>> adj,
                               State[] state, List<Integer> order) {
        state[u] = State.VISITING;
        for (int v : adj.get(u)) {
            if (state[v] == State.VISITING) return false;
            if (state[v] == State.UNVISITED && !dfs(v, adj, state, order))
                return false;
        }
        state[u] = State.VISITED;
        order.add(u);
        return true;
    }
}

const (
    Unvisited = 0
    Visiting  = 1
    Visited   = 2
)

func topoSortDFS(V int, adj [][]int) []int {
    state := make([]int, V)
    order := []int{}

    var dfs func(int) bool
    dfs = func(u int) bool {
        state[u] = Visiting
        for _, v := range adj[u] {
            if state[v] == Visiting {
                return false
            }
            if state[v] == Unvisited && !dfs(v) {
                return false
            }
        }
        state[u] = Visited
        order = append(order, u)
        return true
    }

    for i := 0; i < V; i++ {
        if state[i] == Unvisited && !dfs(i) {
            return nil
        }
    }
    for i, j := 0, len(order)-1; i < j; i, j = i+1, j-1 {
        order[i], order[j] = order[j], order[i]
    }
    return order
}

Phát hiện chu trình trong DAG

Cả hai thuật toán đều phát hiện chu trình: Kahn kiểm tra len(order) < V (còn đỉnh chưa xử lý → tồn tại vòng phụ thuộc), DFS phát hiện back edge (đỉnh VISITING gặp lại đỉnh VISITING). Kahn dễ trích xuất các đỉnh nằm trong chu trình (những đỉnh indeg > 0 còn lại), DFS dễ trích xuất đường đi của chu trình.

Thực chiến

Tình huống 1: Build system — xác định thứ tự compile

Bối cảnh: Hệ thống build có N module, mỗi module khai báo dependency. Cần tìm thứ tự compile hợp lệ và phát hiện circular dependency.

python

from collections import deque, defaultdict
from dataclasses import dataclass

@dataclass
class Module:
    name: str
    depends_on: list[str]

def resolve_build_order(modules: list[Module]) -> list[str]:
    adj: dict[str, list[str]] = defaultdict(list)
    indeg: dict[str, int] = defaultdict(int)
    all_names: set[str] = set()

    for m in modules:
        all_names.add(m.name)
        indeg.setdefault(m.name, 0)
        for dep in m.depends_on:
            all_names.add(dep)
            adj[dep].append(m.name)
            indeg[m.name] += 1
            indeg.setdefault(dep, 0)

    q = deque(n for n in all_names if indeg[n] == 0)
    order: list[str] = []

    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    if len(order) != len(all_names):
        stuck = [n for n in all_names if indeg[n] > 0]
        raise ValueError(f"Circular dependency involving: {stuck}")

    return order

Phân tích: Dùng Kahn vì dễ song song hóa — tất cả đỉnh cùng level chạy đồng thời — và khi phát hiện cycle, in-degree còn lại cho biết chính xác đỉnh nào dính vòng.

Tình huống 2: Course prerequisite — lập kế hoạch học kỳ

Bối cảnh: Sinh viên cần hoàn thành N môn, mỗi môn có prerequisite. Trả về thứ tự học hợp lệ hoặc thông báo không thể tốt nghiệp.

python

def plan_semesters(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    adj = [[] for _ in range(num_courses)]
    indeg = [0] * num_courses

    for course, prereq in prerequisites:
        adj[prereq].append(course)
        indeg[course] += 1

    q = deque(i for i in range(num_courses) if indeg[i] == 0)
    order: list[int] = []

    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    return order if len(order) == num_courses else []

Sai lầm điển hình

❌ Sai lầm 1: Quên kiểm tra chu trình

Vấn đề: Áp dụng topological sort mà không verify DAG.

python

# SAI: không kiểm tra cycle — kết quả thiếu đỉnh mà không báo lỗi
def topo_sort_no_check(V, adj):
    indeg = [0] * V
    for u in range(V):
        for v in adj[u]:
            indeg[v] += 1
    q = deque(i for i in range(V) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order  # có thể thiếu đỉnh nếu có cycle!

Tại sao sai: Trong production, circular dependency là lỗi nghiêm trọng. Nếu không kiểm tra, build system chạy một phần rồi fail giữa chừng — debug cực khó.

python

# ĐÚNG: luôn kiểm tra len(order) == V
if len(order) != V:
    raise ValueError("Graph contains a cycle")
return order

❌ Sai lầm 2: DFS chỉ dùng boolean visited

Vấn đề: Chỉ dùng visited boolean thay vì 3 trạng thái.

python

# SAI: visited boolean không phân biệt back edge vs cross edge
visited = [False] * V
def dfs(u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v)
    order.append(u)

Tại sao sai: Với visited boolean, bạn không phát hiện được chu trình. Đỉnh đã visit (VISITED) và đỉnh đang trong call stack (VISITING) cần phân biệt — chỉ VISITING → VISITING mới là back edge (chu trình).

python

# ĐÚNG: 3 trạng thái UNVISITED, VISITING, VISITED
state = [UNVISITED] * V
def dfs(u):
    state[u] = VISITING
    for v in adj[u]:
        if state[v] == VISITING:
            return False  # back edge → cycle
        if state[v] == UNVISITED and not dfs(v):
            return False
    state[u] = VISITED
    order.append(u)
    return True

❌ Sai lầm 3: Quên reverse kết quả DFS

Vấn đề: DFS append khi hoàn thành, nên thứ tự ngược.

python

# SAI: trả về order mà không reverse
return order  # ngược! Đỉnh hoàn thành sau được append sau

Tại sao sai: DFS post-order cho thứ tự reverse topological. Đỉnh "lá" (không phụ thuộc ai) hoàn thành trước, được append trước — nhưng nó phải đứng cuối trong topological order.

python

# ĐÚNG: reverse sau khi duyệt xong
return order[::-1]

❌ Sai lầm 4: Nhầm hướng cạnh dependency

Vấn đề: Khi xây đồ thị từ danh sách dependency, nhầm chiều u → v.

python

# SAI: "A phụ thuộc B" mà thêm cạnh A → B
for module in modules:
    for dep in module.depends_on:
        adj[module.name].append(dep)  # ngược!

Tại sao sai: "A phụ thuộc B" nghĩa là B phải xử lý trước A → cạnh B → A. Nhầm hướng cho kết quả đảo ngược hoàn toàn.

python

# ĐÚNG: dependency → dependent
for module in modules:
    for dep in module.depends_on:
        adj[dep].append(module.name)  # B → A

Under the Hood

Hiệu năng

Thuật toán	Time	Space	Ghi chú
Kahn (BFS)	O(V + E)	O(V + E)	Dễ parallelism, dễ detect cycle nodes
DFS-based	O(V + E)	O(V + E)	Stack space O(V) worst case, dễ trace cycle path

Cả hai đều tối ưu — không thể làm tốt hơn O(V+E) vì phải visit mọi đỉnh và cạnh ít nhất một lần.

Tính duy nhất của thứ tự

Topological order không duy nhất trừ khi đồ thị là một chuỗi duy nhất (Hamiltonian path trong DAG). Nếu tại bất kỳ bước nào queue/stack có nhiều hơn 1 đỉnh khả dụng, mỗi lựa chọn cho một thứ tự khác nhau.

Lexicographic topological sort: Thay queue bằng priority queue (min-heap) trong Kahn → luôn chọn đỉnh nhỏ nhất. Complexity tăng lên O((V+E) log V), hữu ích khi đề bài yêu cầu thứ tự từ điển nhỏ nhất.

Kahn vs DFS — khi nào dùng gì?

Tiêu chí	Kahn (BFS)	DFS
Parallel scheduling	✅ Tự nhiên — cùng level chạy đồng thời	❌ Cần thêm logic
Detect cycle nodes	✅ indeg > 0 còn lại	Phức tạp hơn
Trace cycle path	Cần thêm logic	✅ Tự nhiên qua call stack
Lexicographic order	✅ Thay queue bằng min-heap	Khó hơn
Đơn giản	✅ Iterative, dễ debug	Recursive, cẩn thận stack overflow

Quy tắc thực hành: Kahn cho hầu hết production use case. DFS khi cần trace cycle path hoặc kết hợp với bài toán DFS tree khác (SCC, etc.).

Checklist ghi nhớ

✅ Checklist triển khai

Nền tảng

[ ] Topological sort chỉ áp dụng cho DAG — đồ thị có hướng không chu trình
[ ] Kahn: đếm in-degree → queue đỉnh in-degree 0 → giảm in-degree neighbor → lặp
[ ] DFS: post-order append → reverse = topological order
[ ] Luôn kiểm tra cycle: len(order) != V (Kahn) hoặc back edge (DFS)

Triển khai

[ ] 3 trạng thái cho DFS: UNVISITED, VISITING, VISITED — không dùng boolean
[ ] Hướng cạnh: dependency → dependent, không phải ngược lại
[ ] Lexicographic sort: thay queue bằng priority_queue trong Kahn

Ứng dụng

[ ] Build system, package manager, CI/CD pipeline
[ ] Course scheduling, task dependency resolution
[ ] Spreadsheet cell evaluation order
[ ] Parallel scheduling: nhóm đỉnh cùng level để chạy đồng thời

Bài tập luyện tập

Bài 1: Course Schedule — Foundation

Đề bài: Cho numCourses và danh sách prerequisites[i] = [a, b] nghĩa là phải học b trước a. Trả về true nếu có thể hoàn thành tất cả môn học. (LeetCode 207)

🧠 Quiz

Topological sort trên đồ thị có chu trình sẽ cho kết quả gì?

[ ] A. Exception / crash
[x] B. Danh sách kết quả có ít hơn V phần tử (Kahn) hoặc phát hiện back edge (DFS)
[ ] C. Kết quả ngẫu nhiên
[ ] D. Vòng lặp vô hạn Giải thích: Kahn dừng khi queue rỗng — nếu còn đỉnh có in-degree > 0 thì len(order) < V. DFS phát hiện back edge khi gặp đỉnh VISITING. Không có crash hay infinite loop nếu cài đặt đúng.

💡 Gợi ý

Xây đồ thị từ prerequisites, chạy Kahn hoặc DFS
Kiểm tra len(order) == numCourses
Cạnh: b → a (học b trước a)

✅ Lời giải

python

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    adj = [[] for _ in range(numCourses)]
    indeg = [0] * numCourses
    for a, b in prerequisites:
        adj[b].append(a)
        indeg[a] += 1
    q = deque(i for i in range(numCourses) if indeg[i] == 0)
    count = 0
    while q:
        u = q.popleft()
        count += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return count == numCourses

Phân tích: O(V + E) time, O(V + E) space.

Bài 2: Alien Dictionary — Intermediate

Đề bài: Cho danh sách từ words đã sort theo thứ tự từ điển ngoài hành tinh. Tìm thứ tự các ký tự. Trả về "" nếu không hợp lệ. (LeetCode 269)

💡 Gợi ý

So sánh từng cặp từ liên tiếp, tìm ký tự khác nhau đầu tiên → cạnh trong DAG
Topological sort trên DAG ký tự
Edge case: ["abc", "ab"] → không hợp lệ (từ ngắn hơn phải đứng trước)

✅ Lời giải

python

def alienOrder(words: list[str]) -> str:
    adj: dict[str, set[str]] = {c: set() for w in words for c in w}
    indeg = {c: 0 for c in adj}

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        if len(w1) > len(w2) and w1[:len(w2)] == w2:
            return ""
        for c1, c2 in zip(w1, w2):
            if c1 != c2:
                if c2 not in adj[c1]:
                    adj[c1].add(c2)
                    indeg[c2] += 1
                break

    q = deque(c for c in indeg if indeg[c] == 0)
    result = []
    while q:
        c = q.popleft()
        result.append(c)
        for nei in adj[c]:
            indeg[nei] -= 1
            if indeg[nei] == 0:
                q.append(nei)

    return "".join(result) if len(result) == len(indeg) else ""

Phân tích: O(C) với C = tổng độ dài các từ. Bài toán kinh điển minh họa topological sort trên character graph.

Liên kết học tiếp

Từ khóa glossary: topological sort, sắp xếp topo, DAG, Kahn, in-degree, dependency resolution

Tìm kiếm liên quan: sắp xếp phụ thuộc, thứ tự build, course schedule, detect cycle DAG

Topological Sort — Sắp xếp phụ thuộc ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Kahn's Algorithm — BFS với in-degree ​

DFS-based Topological Sort ​

Phát hiện chu trình trong DAG ​

Thực chiến ​

Tình huống 1: Build system — xác định thứ tự compile ​

Tình huống 2: Course prerequisite — lập kế hoạch học kỳ ​

Sai lầm điển hình ​

❌ Sai lầm 1: Quên kiểm tra chu trình ​

❌ Sai lầm 2: DFS chỉ dùng boolean visited ​

❌ Sai lầm 3: Quên reverse kết quả DFS ​

❌ Sai lầm 4: Nhầm hướng cạnh dependency ​

Under the Hood ​

Hiệu năng ​

Tính duy nhất của thứ tự ​

Kahn vs DFS — khi nào dùng gì? ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Course Schedule — Foundation ​

Bài 2: Alien Dictionary — Intermediate ​

Liên kết học tiếp ​

Topological Sort — Sắp xếp phụ thuộc

Bức tranh tư duy

Cốt lõi kỹ thuật

Kahn's Algorithm — BFS với in-degree

DFS-based Topological Sort

Phát hiện chu trình trong DAG

Thực chiến

Tình huống 1: Build system — xác định thứ tự compile

Tình huống 2: Course prerequisite — lập kế hoạch học kỳ

Sai lầm điển hình

❌ Sai lầm 1: Quên kiểm tra chu trình

❌ Sai lầm 2: DFS chỉ dùng boolean visited

❌ Sai lầm 3: Quên reverse kết quả DFS

❌ Sai lầm 4: Nhầm hướng cạnh dependency

Under the Hood

Hiệu năng

Tính duy nhất của thứ tự

Kahn vs DFS — khi nào dùng gì?

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Course Schedule — Foundation

Bài 2: Alien Dictionary — Intermediate

Liên kết học tiếp