首页 > 编程语言 >【C++算法模板】图论-拓扑排序,超详细注释带例题

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

时间:2024-03-16 10:59:06浏览次数:28  
标签:图论 int 拓扑 入度 ne tp C++ 顶点 例题

文章目录

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

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} 都是合法的拓扑序

在这里插入图片描述

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

1)Kahn算法

  • 算法核心:用队列维护一个入度为 0 0 0 的节点的集合
  1. 初始化(链式前向星建图建边),队列 q q q 压入所有入度为 0 0 0 的点
  2. 每次从 q q q 中取出队头 x x x 放入数组 t p tp tp , t p tp tp 数组保存出队顺序,也就是拓扑序
  3. 然后将 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 维护
  4. 不断重复 2 , 3 2,3 2,3 过程,直到队列 q q q 为空
  5. 若 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 经历三次变色
  1. 初始化:将所有点染色为 0 0 0
  2. 枚举每个点,进入点 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
  3. 如果枚举完 x x x 的所有儿子节点都没有发现环,则把 x x x 染色为 1 1 1,并把 x x x 压入 t p tp tp 数组
  4. 注意,因为 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

题目链接: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;
}

标签:图论,int,拓扑,入度,ne,tp,C++,顶点,例题
From: https://blog.csdn.net/qq_63586399/article/details/136749902

相关文章

  • C++函数调用优化
    C++函数调用优化施磊老师网课笔记截图1、用临时对象拷贝构造一个新对象的时候,编译器会对其优化,直接用生成临时对象的方法构造新对象;......
  • C++ Function Templates (函数模板)
    C++FunctionTemplates[函数模板]1.TemplatesandGenericProgramming(模板与泛型编程)2.DefiningaFunctionTemplates(定义函数模板)2.1.InstantiatingaFunctionTemplate(实例化函数模板)2.2.TemplateTypeParameters(模板类型参数)2.3.Non......
  • KMP字符串(解释+例题)
    题目描述:  思路: 数据结构KMP算法配图详解(超详细)_kmp算法流程图-CSDN博客AcWing831.字符串查找---用16幅图从暴力一步步优化到KMP-AcWing推荐以上两篇大佬的文章kmp算法步骤(p子串和s串下标从1开始):1、kmp匹配过程首先需要了解什么是前缀和后缀(只针对p子串去......
  • C++list实现
    长话短说,我们直接实现。#pragmaonce#include<assert.h>namespacecx{ template<classT> structListNode { //构造函数 ListNode(constT&x=T()) :_next(nullptr),_prev(nullptr),_val(x) {} //成员变量: ListNode<T>*_next; ListNode<T&......
  • 图论——倍增LCA 学习笔记
    图论——倍增LCA学习笔记定义最近公共祖先,简称LCA(LowestCommonAncestor)。一个集合\(S\)的最近公共祖先\(\text{LCA}(S)=\text{LCA}(s_1,s_2,\dots,s_k)\)定义为:这个集合中所有节点,其祖先的交集中,离根最远的那个。性质在数值的关系上:\(\text{LCA}(\{u\})=u\);\(\t......
  • c++ 画规律画
     1#include<iostream>2usingnamespacestd;3intmain(intargc,char**argv){4intn;5cin>>n;6//三角7for(inti=1;i<=n;i++){8for(intt=1;t<=n-i;t++){9cout<<"";......
  • 大规模C++程序设计 -- 基础知识
    基础知识我们先回顾C++程序语言和面向对象分析的一些重要的方面,这些知识对于大型系统设计来说是基本的。我们仔细分析多文件程序、声明与定义,以及在头文件和实现文件上下文中的内部链接和外部链接,然后研究typedef和assert的使用。多文件C++程序对于所有的(除了最小的)程序来说,将......
  • c++高精度减法的方法和示例代码
    C++中的高精度减法指的是在处理大数时,执行减法操作的方法。通常情况下,C++内置的数据类型(如int、long、double等)可能无法满足大数运算的需求,因为它们的范围有限。在这种情况下,需要使用自定义的数据结构或者字符串来表示大数,并实现相应的算术操作。以下是执行高精度减法的基本思......
  • 【C++进阶】C++关联式容器map和set用法详解
    map和set用法详解一,关联式容器二,键值对pair三,set1.set的用法2.multiset的用法四,map1.键值对pair的介绍2.map用法3.multimap用法五,总结上一节我们讲解了二叉搜索树,在讲解之前我们先来讲一下set和map,因为set和map的底层是AVL树和红黑树,而AVL树和红黑树又是一种二......
  • 图论:DFS与BFS
    目录1.DFS(图论)1.1.DFS过程1.2.应用2.BFS(图论)2.1.BFS过程2.2.应用2.3.双端队列BFS实现2.4.优先队列BFS(堆优化Dijkstra算法)1.DFS(图论)DFS全称是,中文名是深度优先搜索,是一种用于遍历或搜索树或图的算法。所谓深度优先,就是说每次都尝试向更深的节点走。广义上的DFS:DF......