拓扑排序

• 0. 概述
• 1. Kahn算法
  • 1.1. 数据结构
  • 1.2. 建图
  • 1.3. Kanh算法
• 2. DFS染色
  • 2.1. 数据结构
  • 2.2. 建图
  • 2.3. DFS
• 3. 算法对比
• 4. 【例题】洛谷 B3644

推荐视频链接：D01 拓扑排序

0. 概述

• 给定一张有向无环图，排出所有顶点的一个序列 $A$ 满足：对于图中的每条有向边 $(x,y)$，$x$ 在 $A$ 中都出现在 $y$ 之前，则称 $A$ 是该图的顶点的一个拓扑序

• 拓扑排序 可以判断有向图中是否有环，可以生成拓扑序列

• 对于下图，${2,3,5,1,7,4,6}$ 和 ${3,2,1,5,7,6,4}$ 都是合法的拓扑序

复习一下链式前向星吧：【C++算法模板】图的存储-邻接表，手撕链式前向星，超详细代码注释-CSDN博客

1. Kahn算法

• 算法核心：用队列维护一个入度为 $0$ 的节点的集合

1. 初始化（链式前向星建图建边），队列 $q$ 压入所有入度为 $0$ 的点
2. 每次从 $q$ 中取出队头 $x$ 放入数组 $tp$ ，$tp$ 数组保存出队顺序，也就是拓扑序
3. 然后将 $x$ 的所有出边删除，如删除边 $(x,y)$ ，$y$ 的入度则 $-1$，如果 $y$ 的入度变为 $0$，则将 $y$ 压入 $q$ 中，其中每个顶点的入度用数组 $d$ 维护
4. 不断重复 $2,3$ 过程，直到队列 $q$ 为空
5. 若 $tp$ 中的元素个数等于 $n$，则有拓扑序；否则，有环

1.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; // 边的编号,建边因子

1.2. 建图

// 链式前向星
void add(int a,int b) {
	e[idx]=b;
	ne[idx]=h[a]; // 头插法思想
	h[a]=idx++;
}

1.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染色

• 算法核心：在于染色法，每次 $dfs$ 搜索会给点变色，如果有拓扑序，每个点的颜色都会从 $0→-1→1$ 经历三次变色

1. 初始化：将所有点染色为 $0$
2. 枚举每个点，进入点 $x$，将 $x$ 染色为 $-1$，随后枚举 $x$ 的所有儿子结点 $y$，如果 $y$ 的颜色仍为 $0$，说明该点未被遍历过，则递归到下一层；如果 $y$ 的颜色为 $-1$，说明遍历到祖先节点了，即出现了环，则直接 $return$
3. 如果枚举完 $x$ 的所有儿子节点都没有发现环，则把 $x$ 染色为 $1$，并把 $x$ 压入 $tp$ 数组
4. 注意，因为 $DFS$ 是栈实现的，回溯的时候才把点加入 $tp$ 数组，所以需要将 $tp$ 数组逆序才能得到拓扑序

2.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.2. 建图

// 链式前向星
void add(int a,int b) {
	e[idx]=b;
	ne[idx]=h[a]; // 头插法思想
	h[a]=idx++;
}

2.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. 算法对比

• 在实际使用拓扑排序时只需要掌握 $Kahn$ 即可，因为更好理解，$DFS$ 染色和二分图中的匈牙利算法的思想比较类似，这里只用了解即可
  • $Kahn$：队列维护，顺着拓扑序收集点
  • $DFS$：系统栈维护，逆着拓扑序收集点
• 二者时间复杂度都为 $O(E+V)$，其中 $E$ 为边数，$V$ 为点数

4. 【例题】洛谷 B3644

题目链接：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;
}
/*
5边,接下来第i行表示节点i的后代,0表示输入完毕
输入样例:
5
0
4 5 1 0
1 0
5 3 0
3 0
输出样例:
2 4 5 3 1
*/

打赏