【C++算法模板】图论-拓扑排序，超详细注释带例题-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C++算法模板】图论-拓扑排序，超详细注释带例题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

0）概述

给定一张有向无环图，排出所有顶点的一个序列 $A$ 满足：对于图中的每条有向边 $(x, y)$ ， $x$ 在 $A$ 中都出现在 $y$ 之前，则称 $A$ 是该图的顶点的一个拓扑序
拓扑排序可以判断有向图中是否有环，可以生成拓扑序列
对于下图， ${2,3,5,1,7,4,6\}$ 和 ${3,2,1,5,7,6,4\}$ 都是合法的拓扑序

拓扑序列c++模板,C++算法竞赛,算法,c++,图论,拓扑排序,算法竞赛,图搜索算法

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

1）Kahn算法

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

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

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

初始化：将所有点染色为 $0$
枚举每个点，进入点 $x$ ，将 $x$ 染色为 $- 1$ ，随后枚举 $x$ 的所有儿子结点 $y$ ，如果 $y$ 的颜色仍为 $0$ ，说明该点未被遍历过，则递归到下一层；如果 $y$ 的颜色为 $- 1$ ，说明遍历到祖先节点了，即出现了环，则直接 $re t u r n$
如果枚举完 $x$ 的所有儿子节点都没有发现环，则把 $x$ 染色为 $1$ ，并把 $x$ 压入 $tp$ 数组
注意，因为 $D FS$ 是栈实现的，回溯的时候才把点加入 $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 ahn$ 即可，因为更好理解， $D FS$ 染色和二分图中的匈牙利算法的思想比较类似，这里只用了解即可
- $K ahn$ ：队列维护，顺着拓扑序收集点
- $D FS$ ：系统栈维护，逆着拓扑序收集点
二者时间复杂度都为 $O (E + V)$ ，其中 $E$ 为边数， $V$ 为点数

【例题】洛谷 B3644

题目链接：B3644 【模板】拓扑排序 / 家谱树 - 洛谷文章来源地址https://www.toymoban.com/news/detail-852291.html

#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;
}