Sắp xếp tô-pô (Topological Sort)
Sắp xếp các đỉnh của đồ thị có hướng sao cho mọi cung đi từ trước ra sau: thuật toán Kahn, DFS ba màu, phát hiện chu trình, thứ tự nhỏ nhất theo từ điển và quy hoạch động trên DAG.
Sắp xếp tô-pô (topological sort) của một đồ thị có hướng là cách xếp tất cả các đỉnh thành một dãy sao cho với mọi cung , đỉnh đứng trước . Đây là cách diễn đạt chung cho mọi bài "việc này phải làm trước việc kia": thứ tự học các môn có điều kiện tiên quyết, thứ tự biên dịch các tệp phụ thuộc nhau, thứ tự chữ cái suy ra từ một danh sách đã sắp...
Một đồ thị có thứ tự tô-pô khi và chỉ khi nó không có chu trình (DAG, Directed Acyclic Graph). Hai thuật toán chuẩn là Kahn (lần lượt lấy đỉnh không còn cung vào) và DFS (đảo ngược thứ tự thăm xong), cả hai chạy và đồng thời phát hiện chu trình. Thứ tự tô-pô còn là "xương sống" của quy hoạch động trên DAG: đường đi dài nhất, đếm số đường đi, giá trị Grundy của trò chơi trên đồ thị... đều tính theo thứ tự này.
Ý tưởng / Trực giác
Vì sao có chu trình thì không sắp được? Nếu thì phải đứng trước , ..., đứng trước : mâu thuẫn.
Vì sao DAG luôn sắp được? Mọi DAG khác rỗng có ít nhất một đỉnh bậc vào 0 (nguồn): nếu đỉnh nào cũng có cung vào, đi ngược cung mãi thì sau tối đa bước phải lặp lại một đỉnh, tạo chu trình. Đặt một nguồn lên đầu dãy, xóa nó cùng các cung ra của nó, phần còn lại vẫn là DAG; lặp lại.
Thuật toán Kahn chính là lập luận trên: duy trì bậc vào và một hàng đợi các đỉnh có bậc vào . Lấy một đỉnh ra, ghi vào kết quả, giảm bậc vào của mọi mà ; đỉnh nào về thì vào hàng đợi. Nếu kết thúc mà chưa lấy đủ đỉnh, các đỉnh còn lại đều có bậc vào dương trong phần đồ thị còn lại, theo lập luận trên phần đó chứa chu trình.
Thuật toán DFS. Chạy DFS, ghi đỉnh vào danh sách post lúc thăm xong (mọi đỉnh đi tới được từ đã xong). Với cung trong DAG, khi DFS xét cung này thì hoặc chưa thăm (sẽ được thăm và xong trước ), hoặc đã xong (xong trước ). không thể "đang mở" (còn trên ngăn xếp) vì như vậy có đường , tức chu trình. Vậy luôn xong trước , và đảo ngược post cho thứ tự tô-pô. Để phát hiện chu trình, tô ba màu: trắng (chưa thăm), xám (đang mở), đen (đã xong); gặp cung tới đỉnh xám là có chu trình.
Thứ tự nhỏ nhất theo từ điển. Thay hàng đợi trong Kahn bằng min-heap: mỗi bước lấy nguồn nhỏ nhất. Tham lam này đúng vì đỉnh đầu tiên của mọi thứ tự hợp lệ phải là một nguồn, nên vị trí đầu nhỏ nhất có thể đúng bằng nguồn nhỏ nhất; sau khi chọn nó, bài toán còn lại có cùng dạng. Chú ý: không có cách "DFS rồi sắp xếp" nào cho ra thứ tự này.
DP trên DAG. Nếu chỉ phụ thuộc vào của các cung (ví dụ ), xét các đỉnh theo thứ tự tô-pô thì khi tới , mọi cần dùng đã được tính xong. Ngược lại, nếu phụ thuộc vào các đỉnh đi tới (như giá trị Grundy: ) thì duyệt theo thứ tự tô-pô đảo ngược.
Ví dụ chạy tay
Đồ thị 6 đỉnh, 7 cung:
3 ----> 2 ----> 1
| |
| v
+-----> 6 ----> 4
^ ^
| |
5 ------+-------+
Các cung: , , , , , , . Bậc vào ban đầu:
| Đỉnh | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| indeg | 1 | 1 | 0 | 2 | 0 | 3 |
Kahn (hàng đợi FIFO):
| Bước | Lấy ra | Cập nhật bậc vào | Hàng đợi sau bước |
|---|---|---|---|
| 0 | [3, 5] | ||
| 1 | 3 | 2: 1→0 (vào hàng đợi), 6: 3→2 | [5, 2] |
| 2 | 5 | 4: 2→1, 6: 2→1 | [2] |
| 3 | 2 | 1: 1→0, 6: 1→0 | [1, 6] |
| 4 | 1 | [6] | |
| 5 | 6 | 4: 1→0 | [4] |
| 6 | 4 | [] |
Kết quả: 3 5 2 1 6 4.
Kahn với min-heap (thứ tự nhỏ nhất theo từ điển): heap , lấy 3 (thả 2) thành , lấy 2 (thả 1) thành , lấy 1, lấy 5 (thả 6), lấy 6 (thả 4), lấy 4. Kết quả: 3 2 1 5 6 4, nhỏ hơn kết quả FIFO ở vị trí thứ hai.
DFS (bắt đầu lần lượt từ đỉnh 1, 2, ...): thăm 1, xong 1. Thăm 2, cung tới 1 (đã xong), cung tới 6, thăm 6, thăm 4, xong 4, xong 6, xong 2. Thăm 3, cả hai cung tới đỉnh đã xong, xong 3. Thăm 5, xong 5. Danh sách thăm xong là ; đảo ngược được 5 3 2 6 4 1.
Ba kết quả khác nhau nhưng đều hợp lệ: một DAG thường có rất nhiều thứ tự tô-pô.
Đường đi dài nhất (mỗi cung dài 1): theo thứ tự 3 5 2 1 6 4, , , , , . Đường dài nhất có 3 cung: .
Có chu trình: thêm cung . Khi đó là chu trình, bậc vào của 3 thành 1, nguồn duy nhất là 5. Kahn lấy 5 ra rồi kẹt (bậc vào của 4 và 6 vẫn dương), chỉ lấy được 1 trong 6 đỉnh nên báo . DFS cũng báo : khi đang mở 3, 6, 4 thì cung trỏ về đỉnh xám.
Cài đặt
Mọi chương trình đọc , rồi cung (đỉnh , cho phép cung lặp và khuyên), in một thứ tự tô-pô hoặc nếu có chu trình. DFS viết không đệ quy để chạy được trên đồ thị dạng đường thẳng .
Thuật toán Kahn
#include <bits/stdc++.h>
using namespace std;
// Thuật toán Kahn: in một thứ tự topo, hoặc -1 nếu đồ thị có chu trình.
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
indeg[v]++; // cung lặp được đếm nhiều lần, khớp với số lần bị xóa
}
vector<int> order; // dùng luôn làm hàng đợi: đầu hàng đợi là chỉ số head
for (int v = 1; v <= n; v++)
if (indeg[v] == 0) order.push_back(v);
for (size_t head = 0; head < order.size(); head++) {
int u = order[head];
for (int v : adj[u])
if (--indeg[v] == 0) order.push_back(v); // v hết cung vào: sẵn sàng
}
if ((int)order.size() < n) { // còn đỉnh kẹt lại: chúng nằm trên hoặc sau một chu trình
cout << -1 << "\n";
return 0;
}
for (int i = 0; i < n; i++) cout << order[i] << (i + 1 < n ? ' ' : '\n');
}
import sys
def main():
# Thuật toán Kahn: in một thứ tự topo, hoặc -1 nếu đồ thị có chu trình.
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append(v)
indeg[v] += 1 # cung lặp được đếm nhiều lần, khớp với số lần bị xóa
order = [v for v in range(1, n + 1) if indeg[v] == 0]
head = 0 # order dùng luôn làm hàng đợi
while head < len(order):
u = order[head]
head += 1
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0: # v hết cung vào: sẵn sàng
order.append(v)
if len(order) < n: # còn đỉnh kẹt lại: chúng nằm trên hoặc sau một chu trình
print(-1)
else:
print(*order)
main()
DFS ba màu
#include <bits/stdc++.h>
using namespace std;
// Sắp xếp topo bằng DFS (không đệ quy), tô ba màu để phát hiện chu trình.
// color: 0 = chưa thăm, 1 = đang trên ngăn xếp DFS, 2 = đã xong.
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
vector<int> color(n + 1, 0), it(n + 1, 0), post; // post: thứ tự thăm xong
bool cycle = false;
for (int s = 1; s <= n && !cycle; s++) {
if (color[s] != 0) continue;
vector<int> st = {s};
color[s] = 1;
while (!st.empty() && !cycle) {
int u = st.back();
if (it[u] < (int)adj[u].size()) {
int v = adj[u][it[u]++];
if (color[v] == 1) cycle = true; // cung ngược: gặp lại đỉnh đang mở
else if (color[v] == 0) color[v] = 1, st.push_back(v);
} else {
color[u] = 2; // mọi đỉnh đi tới được từ u đã xong trước u
post.push_back(u);
st.pop_back();
}
}
}
if (cycle) {
cout << -1 << "\n";
return 0;
}
reverse(post.begin(), post.end()); // đảo thứ tự thăm xong là thứ tự topo
for (int i = 0; i < n; i++) cout << post[i] << (i + 1 < n ? ' ' : '\n');
}
import sys
def main():
# Sắp xếp topo bằng DFS (không đệ quy), tô ba màu để phát hiện chu trình.
# color: 0 = chưa thăm, 1 = đang trên ngăn xếp DFS, 2 = đã xong.
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
for i in range(m):
adj[int(data[2 + 2 * i])].append(int(data[3 + 2 * i]))
color = [0] * (n + 1)
it = [0] * (n + 1)
post = [] # thứ tự thăm xong
for s in range(1, n + 1):
if color[s]:
continue
st = [s]
color[s] = 1
while st:
u = st[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]
it[u] += 1
if color[v] == 1: # cung ngược: gặp lại đỉnh đang mở
print(-1)
return
if color[v] == 0:
color[v] = 1
st.append(v)
else:
color[u] = 2 # mọi đỉnh đi tới được từ u đã xong trước u
post.append(u)
st.pop()
print(*reversed(post)) # đảo thứ tự thăm xong là thứ tự topo
main()
Thứ tự nhỏ nhất theo từ điển
#include <bits/stdc++.h>
using namespace std;
// Thứ tự topo nhỏ nhất theo từ điển: Kahn với hàng đợi ưu tiên (lấy đỉnh nhỏ nhất).
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
indeg[v]++;
}
priority_queue<int, vector<int>, greater<int>> pq; // min-heap
for (int v = 1; v <= n; v++)
if (indeg[v] == 0) pq.push(v);
vector<int> order;
while (!pq.empty()) {
int u = pq.top();
pq.pop();
order.push_back(u);
for (int v : adj[u])
if (--indeg[v] == 0) pq.push(v);
}
if ((int)order.size() < n) {
cout << -1 << "\n";
return 0;
}
for (int i = 0; i < n; i++) cout << order[i] << (i + 1 < n ? ' ' : '\n');
}
import heapq
import sys
def main():
# Thứ tự topo nhỏ nhất theo từ điển: Kahn với hàng đợi ưu tiên (lấy đỉnh nhỏ nhất).
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append(v)
indeg[v] += 1
pq = [v for v in range(1, n + 1) if indeg[v] == 0]
heapq.heapify(pq) # min-heap
order = []
while pq:
u = heapq.heappop(pq)
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
heapq.heappush(pq, v)
print(-1 if len(order) < n else " ".join(map(str, order)))
main()
Quy hoạch động trên DAG: đường đi nặng nhất
Đầu vào mỗi cung có thêm trọng số (, ); in tổng trọng số lớn nhất của một đường đi bất kỳ.
#include <bits/stdc++.h>
using namespace std;
// DP trên DAG: độ dài (tổng trọng số) lớn nhất của một đường đi bất kỳ, -1 nếu có chu trình.
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<pair<int, long long>>> adj(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
long long w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
indeg[v]++;
}
vector<int> order;
for (int v = 1; v <= n; v++)
if (indeg[v] == 0) order.push_back(v);
for (size_t head = 0; head < order.size(); head++)
for (auto [v, w] : adj[order[head]])
if (--indeg[v] == 0) order.push_back(v);
if ((int)order.size() < n) {
cout << -1 << "\n";
return 0;
}
// best[v] = đường đi nặng nhất kết thúc tại v; xét u theo thứ tự topo nên best[u] đã chốt
vector<long long> best(n + 1, 0);
for (int u : order)
for (auto [v, w] : adj[u]) best[v] = max(best[v], best[u] + w);
cout << *max_element(best.begin() + 1, best.end()) << "\n";
}
import sys
def main():
# DP trên DAG: độ dài (tổng trọng số) lớn nhất của một đường đi bất kỳ, -1 nếu có chu trình.
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for i in range(m):
u, v, w = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
adj[u].append((v, w))
indeg[v] += 1
order = [v for v in range(1, n + 1) if indeg[v] == 0]
head = 0
while head < len(order):
for v, _ in adj[order[head]]:
indeg[v] -= 1
if indeg[v] == 0:
order.append(v)
head += 1
if len(order) < n:
print(-1)
return
# best[v] = đường đi nặng nhất kết thúc tại v; xét u theo thứ tự topo nên best[u] đã chốt
best = [0] * (n + 1)
for u in order:
bu = best[u]
for v, w in adj[u]:
if bu + w > best[v]:
best[v] = bu + w
print(max(best[1:]))
main()
Độ phức tạp
| Thuật toán | Thời gian | Bộ nhớ |
|---|---|---|
| Kahn (hàng đợi) | ||
| DFS ba màu | ||
| Kahn với min-heap (từ điển nhỏ nhất) | ||
| DP trên DAG | sau khi có thứ tự |
Mỗi đỉnh vào và ra hàng đợi (hoặc ngăn xếp) đúng một lần, mỗi cung được xét đúng một lần khi đỉnh đầu của nó được lấy ra (hoặc khi DFS duyệt danh sách kề), nên tổng là . Bản min-heap có thêm lần đẩy và lần lấy ra, mỗi lần .
⚠️ Lỗi thường gặp
- Không kiểm tra chu trình: Kahn trên đồ thị có chu trình vẫn chạy xong và in ra một dãy thiếu đỉnh. Luôn so
order.size()với . Đề "đảm bảo DAG" thì có thể bỏ, nhưng nhiều đề yêu cầu in "IMPOSSIBLE". - DFS chỉ dùng hai màu: đánh dấu "đã thăm" chung cho cả đỉnh đang mở và đỉnh đã xong thì không phân biệt được cung ngược (chu trình) với cung tới nhánh đã xong. Đồ thị , , không có chu trình nhưng bản hai màu dễ báo nhầm; ngược lại bỏ qua mọi đỉnh đã thăm thì không bao giờ phát hiện được chu trình.
- Quên đảo ngược kết quả DFS: thứ tự thăm xong là thứ tự tô-pô ngược. In thẳng
postlà sai (trừ khi bài cần chính thứ tự ngược, như DP Grundy). - DFS đệ quy tràn ngăn xếp: đồ thị dạng đường thẳng với làm đệ quy sâu tầng: C++ có thể tràn ngăn xếp, Python chắc chắn lỗi (giới hạn đệ quy mặc định là 1000). Viết DFS bằng ngăn xếp tự quản như trên, hoặc dùng Kahn.
- Dùng BFS từ một đỉnh thay cho thứ tự tô-pô: khi DP đếm đường đi từ , thứ tự BFS từ không bảo đảm mọi cung vào đã được xử lý trước (ví dụ , , , : BFS có thể xử lý trước ). Phải duyệt theo thứ tự tô-pô.
- Tưởng FIFO cho thứ tự từ điển nhỏ nhất: hàng đợi thường lấy đỉnh theo thứ tự vào hàng, không phải nhỏ nhất. Ví dụ ở trên, FIFO cho 3 5 2 1 6 4 trong khi đáp án nhỏ nhất là 3 2 1 5 6 4. Phải dùng min-heap.
Biến thể / Mở rộng
- Đồ thị có chu trình: nén mỗi thành phần liên thông mạnh thành một đỉnh (SCC), đồ thị nén là DAG và có thể sắp tô-pô. Thuật toán Tarjan cho các SCC theo thứ tự tô-pô ngược. Đây cũng là bước cuối của 2-SAT.
- Thứ tự tô-pô có duy nhất không? Duy nhất khi và chỉ khi trong Kahn, hàng đợi luôn chỉ có đúng một đỉnh; tương đương với việc thứ tự tìm được có cung giữa mọi cặp đỉnh liên tiếp.
- Sắp theo tầng: xử lý Kahn theo từng "lớp" (mọi đỉnh đang có bậc vào 0 cùng lúc) cho số học kỳ tối thiểu để học hết các môn, tức độ dài đường đi dài nhất (tính theo đỉnh).
- Đường đi ngắn nhất trên DAG: cạnh âm vẫn được, chỉ cần một lần DP theo thứ tự tô-pô, nhanh hơn Dijkstra và Bellman-Ford. Xem thêm các dạng DP ở DP trên đồ thị.
- Trò chơi trên DAG: giá trị Grundy tính theo thứ tự tô-pô ngược; tổng nhiều trò chơi độc lập là XOR các giá trị (xem Lý thuyết trò chơi).
- Thứ tự "số 1 đứng sớm nhất có thể": khác với từ điển nhỏ nhất. Cách chuẩn là chạy Kahn trên đồ thị đảo chiều với max-heap, rồi đảo ngược kết quả.
Bài tập luyện
- Sắp xếp topo (gr09_topo): (Medium) In một thứ tự tô-pô của đồ thị có hướng hoặc báo có chu trình; đúng bài thuật toán Kahn.
- Thứ tự topo nhỏ nhất (gr09_lextopo): (Medium) Tìm thứ tự thực hiện công việc nhỏ nhất theo từ điển thỏa mọi yêu cầu trước sau; đúng bài Kahn với min-heap.
- Đếm đường đi trên DAG (gr09_paths): (Hard) Đếm số đường đi từ tới modulo một số; quy hoạch động cộng dồn theo thứ tự tô-pô.
- Tên tác giả (foxnames): (Hard) Tìm một thứ tự của 26 chữ cái để danh sách tên đã cho tăng dần; mỗi cặp tên liên tiếp cho một cung giữa hai chữ cái, đáp án là một thứ tự tô-pô hoặc báo không có nếu gặp chu trình.
- Trò chơi gỗ (icpc21mto): (Very Hard) Trò chơi tổng của hai quân đi trên DAG và một phần chỉ phụ thuộc tính chẵn lẻ; giá trị Grundy của mỗi quân tính bằng cách duyệt ngược thứ tự tô-pô trên đồ thị gốc và đồ thị đảo chiều.
Bình luận