0）概述
-
给定一张有向无环图，排出所有顶点的一个序列 A A A 满足：对于图中的每条有向边 ( x , y ) (x,y) (x,y)， x x x 在 A A A 中都出现在 y y y 之前，则称 A A A 是该图的顶点的一个拓扑序
-
拓扑排序 可以判断有向图中是否有环，可以生成拓扑序列
-
对于下图， { 2 , 3 , 5 , 1 , 7 , 4 , 6 } \{2,3,5,1,7,4,6\} {2,3,5,1,7,4,6} 和 { 3 , 2 , 1 , 5 , 7 , 6 , 4 } \{3,2,1,5,7,6,4\} {3,2,1,5,7,6,4} 都是合法的拓扑序
1）Kahn算法
- 算法核心：用队列维护一个入度为 0 0 0 的节点的集合
- 初始化（链式前向星建图建边），队列 q q q 压入所有入度为 0 0 0 的点
- 每次从 q q q 中取出队头 x x x 放入数组 t p tp tp ， t p tp tp 数组保存出队顺序，也就是拓扑序
- 然后将 x x x 的所有出边删除，如删除边 ( x , y ) (x,y) (x,y) ， y y y 的入度则 − 1 -1 −1，如果 y y y 的入度变为 0 0 0，则将 y y y 压入 q q q 中，其中每个顶点的入度用数组 d d d 维护
- 不断重复 2 , 3 2,3 2,3 过程，直到队列 q q q 为空
- 若 t p tp tp 中的元素个数等于 n n n，则有拓扑序；否则，有环
1：数据结构
const int N=1e5+5; // 最大顶点数
const int M=1e5+10; // 题目中最大边数,拓扑排序是有向图建边,无需×2
int d[N]; // 存储每个顶点的入度
queue<int> q; // 维护入度为0的顶点的队列
queue<int> tp; // 记录q中顶点的出队顺序(拓扑序)
int h[N]; // 存储每个顶点起始边的编号,默认-1表示无边相连
int e[M]; // e[i]:编号为i的边可达的顶点编号
int ne[M]; // ne[i]:编号为i的边的下一条边的编号是ne[i]
int idx; // 边的编号,建边因子
2：建图
// 链式前向星
void add(int a,int b) {
e[idx]=b;
ne[idx]=h[a]; // 头插法思想
h[a]=idx++;
}
3：Kanh算法
// 拓扑序存储于tp队列中,如果能形成拓扑序返回true
bool tuopu() {
for(int i=1;i<=n;i++) {
// 如果入度为0则加入队列
if(d[i]==0) q.push(i);
}
while(q.size()) {
int x=q.front();
q.pop();
tp.push(x); // 出队顺序即拓扑序
// 遍历x的所有出边
for(int i=h[x];i=-1;i=ne[i]) {
int j=e[i];
// 如果去掉边(i,j)后j的入度变为0,则加入队列
if(--d[j]==0) q.push(j);
}
}
return tp.size()==n; // 如果能形成一个拓扑序,返回true,否则false
}
2）DFS染色
- 算法核心：在于染色法，每次 d f s dfs dfs 搜索会给点变色，如果有拓扑序，每个点的颜色都会从 0 → − 1 → 1 0→-1→1 0→−1→1 经历三次变色
- 初始化：将所有点染色为 0 0 0
- 枚举每个点，进入点 x x x，将 x x x 染色为 − 1 -1 −1，随后枚举 x x x 的所有儿子结点 y y y，如果 y y y 的颜色仍为 0 0 0，说明该点未被遍历过，则递归到下一层；如果 y y y 的颜色为 − 1 -1 −1，说明遍历到祖先节点了，即出现了环，则直接 r e t u r n return return
- 如果枚举完 x x x 的所有儿子节点都没有发现环，则把 x x x 染色为 1 1 1，并把 x x x 压入 t p tp tp 数组
- 注意，因为 D F S DFS DFS 是栈实现的，回溯的时候才把点加入 t p tp tp 数组，所以需要将 t p tp tp 数组逆序才能得到拓扑序
1：数据结构
const int N=1e5+5; // 最大顶点数
const int M=1e5+10; // 题目中最大边数,拓扑排序是有向图建边,无需×2
int c[N]; // 存储每个结点的颜色
vector<int> tp; // 存储拓扑序
int h[N]; // 存储每个顶点起始边的编号,默认-1表示无边相连
int e[M]; // e[i]:编号为i的边可达的顶点编号
int ne[M]; // ne[i]:编号为i的边的下一条边的编号是ne[i]
int idx; // 边的编号,建边因子
2：建图
// 链式前向星
void add(int a,int b) {
e[idx]=b;
ne[idx]=h[a]; // 头插法思想
h[a]=idx++;
}
3：DFS
// dfs
bool dfs(int x) {
c[x]=-1; // 先染色为-1
// 遍历所有儿子节点
for(int i=h[x];i=-1;i=ne[i]) {
int j=e[i]; // 取出节点编号
if(c[j]<0) return false; // 遍历到祖先节点,有环,直接return
// 如果没有遍历过
else if(!c[j])
// 继续往下搜,自然结束return 0
if(!dfs(j))
return false;
}
c[x]=1; // 如果能够正常走掉dfs流程,则染色为1
tp.push(x); // 进入拓扑序数组
return true;
}
bool toposort() {
vector<int> tp; // 用vector存储便于反转
memset(c,0,sizeof c); // 染色初始化为0
for(int i=1;i<=n;i++) {
// 如果c没有被走过
if(!c[i])
// 如果遇到环则说明无法形成拓扑序
if(!dfs(i))
return 0;
}
reverse(tp.begin(),tp.end());
return 1;
}
3）算法对比
- 在实际使用拓扑排序时只需要掌握 K a h n Kahn Kahn 即可，因为更好理解， D F S DFS DFS 染色和二分图中的匈牙利算法的思想比较类似，这里只用了解即可
- K a h n Kahn Kahn：队列维护，顺着拓扑序收集点
- D F S DFS DFS：系统栈维护，逆着拓扑序收集点
- 二者时间复杂度都为 O ( E + V ) O(E+V) O(E+V)，其中 E E E 为边数， V V V 为点数
【例题】洛谷 B3644
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
// 解题思路:
const int N=1e5+5; // 最大顶点数
const int M=1e5+10; // 题目中最大边数,拓扑排序是有向图建边,无需×2
int n; // 顶点数
int d[N]; // 存储每个顶点的入度
queue<int> q; // 维护入度为0的顶点的队列
queue<int> tp; // 记录q中顶点的出队顺序(拓扑序)
int h[N]; // 存储每个顶点起始边的编号,默认-1表示无边相连
int e[M]; // e[i]:编号为i的边可达的顶点编号
int ne[M]; // ne[i]:编号为i的边的下一条边的编号是ne[i]
int idx; // 边的编号,建边因子
// 链式前向星
void add(int a,int b) {
e[idx]=b;
ne[idx]=h[a]; // 头插法思想
h[a]=idx++;
}
// 拓扑序存储于tp队列中,如果能形成拓扑序返回true
void tuopu() {
queue<int> q;
for(int i=1;i<=n;i++) {
// 如果入度为0则加入队列
if(d[i]==0)
q.push(i);
}
while(q.size()) {
int x=q.front();
q.pop();
cout<<x<<' '; // 直接输出拓扑序
tp.push(x); // 出队顺序即拓扑序
// 遍历x的所有出边
for(int i=h[x];i!=-1;i=ne[i]) {
int j=e[i];
// 如果去掉边(i,j)后j的入度变为0,则加入队列
if(--d[j]==0) q.push(j);
}
}
}
int main() {
cin>>n;
memset(h,-1,sizeof h); // 链式前向星邻接表初始化
for(int i=1;i<=n;i++) {
int j;
// 当j==0时退出循环
while(cin>>j && j) {
add(i,j);
d[j]++; // 节点j的入度++
}
}
tuopu();
return 0;
}