Giao diện
Topological Sort Advanced
Topological Sort sắp xếp các đỉnh của DAG sao cho với mọi cạnh (u, v), u xuất hiện trước v.
Tại sao Topological Sort?
┌─────────────────────────────────────────────────────────────────┐
│ TOPOLOGICAL SORT APPLICATIONS │
├─────────────────────────────────────────────────────────────────┤
│ │
│ 📦 BUILD SYSTEMS 🎓 COURSE SCHEDULING │
│ ───────────────── ────────────────── │
│ Compile dependencies Prerequisite ordering │
│ Make, Gradle, Bazel Learn A before B │
│ │
│ 🔧 PACKAGE MANAGERS 📋 TASK SCHEDULING │
│ ─────────────────── ──────────────── │
│ npm, pip install order Job dependencies │
│ Resolve dependency tree CI/CD pipeline stages │
│ │
└─────────────────────────────────────────────────────────────────┘Định nghĩa
DAG: Directed Acyclic Graph — Đồ thị có hướng không có chu trình.
Topological Order: Hoán vị các đỉnh sao cho với mọi cạnh u → v, u đứng trước v trong danh sách.
DAG Example Topological Orders
─────────── ──────────────────
A Valid: A → B → C → D → E
↙ ↘ A → C → B → D → E
B C A → B → D → C → E
↘ ↙
D Invalid: B → A → ... (A must come before B)
↓
E⚠️ QUAN TRỌNG
Topological Sort chỉ tồn tại với DAG. Nếu graph có cycle → không thể sắp xếp!
Algorithm 1: Kahn's Algorithm (BFS-based)
Ý tưởng
Sử dụng in-degree (số cạnh đi vào mỗi đỉnh):
- Bắt đầu với các đỉnh có in-degree = 0
- Xóa đỉnh khỏi graph → giảm in-degree của neighbors
- Lặp lại cho đến khi hết đỉnh
┌─────────────────────────────────────────────────────────────────┐
│ KAHN'S ALGORITHM │
├─────────────────────────────────────────────────────────────────┤
│ │
│ 1. Tính in-degree cho mọi đỉnh │
│ 2. Đưa các đỉnh có in-degree = 0 vào queue │
│ 3. While queue not empty: │
│ └─ Pop đỉnh u, thêm vào result │
│ └─ For each neighbor v of u: │
│ ├─ Giảm in-degree[v] │
│ └─ Nếu in-degree[v] == 0 → push v vào queue │
│ 4. Nếu result.size() ≠ V → có cycle! │
│ │
└─────────────────────────────────────────────────────────────────┘Implementation
cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
private:
int V;
vector<vector<int>> adj;
public:
Graph(int vertices) : V(vertices), adj(vertices) {}
void addEdge(int u, int v) {
adj[u].push_back(v); // Directed: u → v
}
// Kahn's Algorithm
vector<int> topologicalSortKahn() {
// Step 1: Calculate in-degree
vector<int> inDegree(V, 0);
for (int u = 0; u < V; ++u) {
for (int v : adj[u]) {
inDegree[v]++;
}
}
// Step 2: Enqueue vertices with in-degree 0
queue<int> q;
for (int i = 0; i < V; ++i) {
if (inDegree[i] == 0) {
q.push(i);
}
}
// Step 3: Process queue
vector<int> result;
while (!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
// Reduce in-degree of neighbors
for (int v : adj[u]) {
inDegree[v]--;
if (inDegree[v] == 0) {
q.push(v);
}
}
}
// Step 4: Check for cycle
if (result.size() != V) {
cout << "⚠️ Graph contains a cycle! No valid topological order." << endl;
return {};
}
return result;
}
};
int main() {
// Example: Course prerequisites
// 0: Calculus I
// 1: Calculus II (requires 0)
// 2: Linear Algebra
// 3: Differential Equations (requires 1, 2)
// 4: Machine Learning (requires 2, 3)
Graph g(5);
g.addEdge(0, 1); // Calc I → Calc II
g.addEdge(1, 3); // Calc II → Diff Eq
g.addEdge(2, 3); // Linear Alg → Diff Eq
g.addEdge(2, 4); // Linear Alg → ML
g.addEdge(3, 4); // Diff Eq → ML
cout << "Courses in order:" << endl;
vector<int> order = g.topologicalSortKahn();
vector<string> names = {
"Calculus I", "Calculus II", "Linear Algebra",
"Differential Equations", "Machine Learning"
};
for (int course : order) {
cout << " " << course << ": " << names[course] << endl;
}
return 0;
}Output:
Courses in order:
0: Calculus I
2: Linear Algebra
1: Calculus II
3: Differential Equations
4: Machine LearningAlgorithm 2: DFS-based Topological Sort
Ý tưởng
DFS + stack: Khi một đỉnh xong hết neighbors, push vào stack. Stack chứa thứ tự ngược.
┌─────────────────────────────────────────────────────────────────┐
│ DFS-BASED APPROACH │
├─────────────────────────────────────────────────────────────────┤
│ │
│ 1. Khởi tạo stack rỗng, visited[] = false │
│ 2. For each unvisited vertex v: │
│ └─ DFS(v): │
│ ├─ Mark v as visited │
│ ├─ For each neighbor u of v: │
│ │ └─ If u not visited → DFS(u) │
│ └─ Push v vào stack // Sau khi xong hết neighbors │
│ 3. Pop hết stack → Topological order │
│ │
└─────────────────────────────────────────────────────────────────┘Implementation với Cycle Detection
cpp
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Graph {
private:
int V;
vector<vector<int>> adj;
// DFS helper with cycle detection
// color: 0 = white (unvisited), 1 = gray (in progress), 2 = black (done)
bool dfs(int u, vector<int>& color, stack<int>& st) {
color[u] = 1; // Mark as in progress
for (int v : adj[u]) {
if (color[v] == 1) {
// Back edge found → cycle!
return false;
}
if (color[v] == 0) {
if (!dfs(v, color, st)) {
return false;
}
}
}
color[u] = 2; // Mark as done
st.push(u); // Push AFTER all neighbors done
return true;
}
public:
Graph(int vertices) : V(vertices), adj(vertices) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
// DFS-based Topological Sort
vector<int> topologicalSortDFS() {
vector<int> color(V, 0); // 0 = white
stack<int> st;
for (int i = 0; i < V; ++i) {
if (color[i] == 0) {
if (!dfs(i, color, st)) {
cout << "⚠️ Graph contains a cycle!" << endl;
return {};
}
}
}
// Pop stack to get topological order
vector<int> result;
while (!st.empty()) {
result.push_back(st.top());
st.pop();
}
return result;
}
};
int main() {
// Build system example
// 0: main.cpp
// 1: utils.h (header)
// 2: utils.cpp (depends on 1)
// 3: app.cpp (depends on 0, 2)
// 4: executable (depends on 3)
Graph g(5);
g.addEdge(1, 2); // utils.h → utils.cpp
g.addEdge(0, 3); // main.cpp → app.cpp
g.addEdge(2, 3); // utils.cpp → app.cpp
g.addEdge(3, 4); // app.cpp → executable
cout << "Build order:" << endl;
vector<int> order = g.topologicalSortDFS();
vector<string> files = {
"main.cpp", "utils.h", "utils.cpp", "app.cpp", "executable"
};
for (int file : order) {
cout << " → " << files[file] << endl;
}
return 0;
}Output:
Build order:
→ main.cpp
→ utils.h
→ utils.cpp
→ app.cpp
→ executableCycle Detection
Cả 2 algorithms đều có thể detect cycle:
| Algorithm | Cycle Detection |
|---|---|
| Kahn's | Nếu result.size() < V → có cycle |
| DFS | Nếu gặp gray node (đang trong stack) → back edge → cycle |
cpp
// Kahn's: Check after processing
if (result.size() != V) {
// Có cycle!
}
// DFS: Check during traversal
if (color[v] == 1) { // Gray = in current DFS path
// Back edge → Cycle!
}So sánh Kahn vs DFS
| Aspect | Kahn's (BFS) | DFS-based |
|---|---|---|
| Approach | In-degree + Queue | Recursion + Stack |
| Time | O(V + E) | O(V + E) |
| Space | O(V) for in-degree + queue | O(V) for color + stack |
| Cycle detect | At end (count check) | During traversal |
| Order | Parallel-friendly | Any valid order |
| Use case | Level-by-level processing | Simple implementation |
⚠️ Common Pitfalls
CẢNH BÁO
1. Quên check cycle:
cpp
// ❌ SAI: Không check cycle
return result; // Có thể return incomplete result!
// ✅ ĐÚNG: Check size
if (result.size() != V) {
throw runtime_error("Graph has cycle!");
}2. Push sai thời điểm (DFS):
cpp
// ❌ SAI: Push trước khi xử lý neighbors
void dfs(int u) {
visited[u] = true;
st.push(u); // SAI! Phải push SAU
for (int v : adj[u]) { ... }
}
// ✅ ĐÚNG: Push SAU khi xong hết neighbors
void dfs(int u) {
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) dfs(v);
}
st.push(u); // ĐÚNG!
}3. Undirected graph không có topological order:
cpp
// Topological sort CHỈ áp dụng cho DIRECTED graph!
// Undirected edge (u-v) luôn tạo "cycle" A→B và B→A🧩 Lexicographically Smallest Order
Nếu cần thứ tự nhỏ nhất về mặt từ điển, dùng priority_queue thay vì queue:
cpp
vector<int> lexicographicallySmallest() {
vector<int> inDegree(V, 0);
for (int u = 0; u < V; ++u) {
for (int v : adj[u]) inDegree[v]++;
}
// Min-heap thay vì queue
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < V; ++i) {
if (inDegree[i] == 0) pq.push(i);
}
vector<int> result;
while (!pq.empty()) {
int u = pq.top();
pq.pop();
result.push_back(u);
for (int v : adj[u]) {
if (--inDegree[v] == 0) {
pq.push(v);
}
}
}
return result;
}🎯 Practice Problems
| Problem | Difficulty | Focus |
|---|---|---|
| Course Schedule (LeetCode 207) | Medium | Cycle detection |
| Course Schedule II (LeetCode 210) | Medium | Return order |
| Alien Dictionary (LeetCode 269) | Hard | Build graph from constraints |
| Parallel Courses (LeetCode 1136) | Medium | Level-based processing |