拓扑排序(所有点按照先后顺序排成序列)
- 注：图必须是有向无环图
Kahn (卡恩) 算法
核心思想：用队列维护一个入度为0的节点的集合
具体代码如下：
vector<int> e[N], tp;
int din[N];
e[x] 用来存点 x 的邻点，tp 存拓扑序列，din[x] 用来存点x的入度
bool toposort() {
queue<int> q;
for(int i = 1; i <= n; i ++)
if(!din[i]) q.push(i); // 压入所有入度为0的点
while(q.size()) {
int x = q.front();
q.pop();
tp.push_back(x);
for(auto y : e[x]) {
if(--din[y] == 0) q.push(y); // 将x的所有出边删除，若y的入度变为0，则将y入队
}
}
return tp.size() == n; // 如果最后tp中的元素不等于个数n，则说明有环
}
主函数操作：
int main() {
cin >> n >> m;
for(int i = 0; i < m; i ++) {
cin >> a >> b;
e[a].push_back(b); // 压入a的邻点b
din[b] ++; // b的入度+1
}
if(!toposort()) cout << "-1" << endl;
else {
for(auto x : tp) {
cout << x << " "; // 遍历输出拓扑序
}
}
return 0;
}
DFS算法
核心思想：染色法 每个点的颜色都会经历从 0 -> -1 -> 1 的染色过程
具体代码如下：
vector<int> e[N], tp;
int c[N]; // 染色数组
e[x] 用来存点 x 的邻点，tp 存拓扑序列，c[x] 存点 x 的颜色
bool dfs(int x) {
c[x] = -1; // -1 表示正在经历
for(auto y : e[x]) {
if(c[y] < 0) return 0; // 为-1说明回到了祖先节点,有环退出
else if(!c[y]) // 没走过继续走
if(!dfs(y)) return 0; // 有环退出
}
c[x] = 1; // 1 表示已经完成
tp.push_back(x); // 完成的点加入tp数组
return 1;
}
void toposort() {
memset(c, 0, sizeof c); // 先让每一个点都染色成0
for(int i = 1; i <= n; i ++) {
if(!c[i]) // 遍历每一个点,如果没走就dfs
if(!dfs(i)) return ; // 判断是否有环
}
reverse(tp.begin(), tp.end()); // dfs是从后往前记录的,所以需要反转下
}
重点
-
Kahn 算法是用队列维护, 顺着拓扑序收集点
-
DFS 算法是用系统栈维护, 逆着拓扑序收集点
-
时间复杂度: \(O(E + V)\ 边数 + 点数\)
-
不是连通也不影响拓扑排序
-
若求字典序最小的拓扑排序,则将 Kahn 算法中的 队列 换成 优先队列(小根堆) 时间复杂度变为 \(O(E + VlogV)\)
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m, a, b;
vector<int> e[N], tp;
int din[N];
void toposort() {
priority_queue<int, vector<int>, greater<int>> q; // 小根堆
for(int i = 1; i <= n; i ++)
if(!din[i]) q.push(i);
while(q.size()) {
int x = q.top();
q.pop();
tp.push_back(x);
for(auto y : e[x]) {
if(--din[y] == 0) q.push(y);
}
}
}
int main() {
cin >> n >> m;
for(int i = 0; i < m; i ++) {
cin >> a >> b;
e[a].push_back(b); // 压入a的邻点b
din[b] ++; // b的入度+1
}
toposort();
for(auto x : tp) {
cout << x << " "; // 遍历输出拓扑序
}
return 0;
}