当前位置:   article > 正文

【图论】拓扑排序:一个名字高大上的实际很简单的算法(图文详解)

【图论】拓扑排序:一个名字高大上的实际很简单的算法(图文详解)

前言

在看到“拓扑序列”这4个字的时候,笔者人是傻的。拓扑序列是啥?听着就感觉好厉害!然后,当我得知“拓扑”两个字其实是一个大家都知道的单词“Top”的音译时,我不禁在想:翻译成这样,估计是故意让大家觉得这个知识点很难的吧。事实证明的确是这样,拓扑排序的概念与实现都是非常简单的。别被看上去高大上的名字吓到了。

拓扑序列概念介绍

首先,我们给出一个如图的有向图
在这里插入图片描述
然后我们给出一个序列a={1,2,3,4},我们随便在有向图中选择一条边,我们都能满足在序列a中,这条边起点的编号一定在终点的编号之前。那么,我们就称为序列a是这个有向图的拓扑序列。

根据拓扑序列的概念,我们能知道:对于某些有向图而言,它的拓扑序列是不唯一的。只要是一个序列满足拓扑序列的定义,我们就可以说这个序列是这张图的拓扑序列。

当然,并不是所有图都是存在拓扑序列的,如果我们发现有向图中存在环,那么无论如何我们也找不出一个序列满足拓扑序列的定义。
在这里插入图片描述

如图,我们发现如果在之前的图中加上一条边,那么这张图就没有拓扑序列了。

拓扑序列求法介绍

首先,我们需要复习(预习?)一下离散数学中的知识点,入度。
所谓入度,就是对于有向图中的一个点而言,有多少个箭头是指向它的的。比如在最上方的没有环的有向图中,点1的入度为0,点2与3的入度都为1,点3的入度为2。

在了解了入度后,我们开始进行拓扑排序,在排序中,我们使用的是BFS广度优先搜索的思路进行点的遍历。
0.初始化:建图,求出所有点的入度。
1.我们首先遍历全图要找到入度为0的点,我们在我们的图中首先找到了点1
在这里插入图片描述
广度遍历所有以1为起点的边,删除这些边,操作为点2的入度减去1,然后就是这样,我们把点1放进拓扑序列中的最前面,a={1};
在这里插入图片描述

再次循环遍历所有还没有放进序列的点,我们发现图中点2的入度已经变成0了,标记出来重复对点1的操作,a={1,2}
在这里插入图片描述

继续遍历,我们找到了点3,操作。a={1,2,3}
在这里插入图片描述

最后找到了点4,所有点都操作完毕,a={1,2,3,4},拓扑排序结束。
在这里插入图片描述

没有拓扑序列的有环图判断

之前我们说过,并不是所有的有向图都存在拓扑序列的,那么我们要怎么来进行判断呢?首先,我们放一个存在环的有向图来进行上述的算法
在这里插入图片描述
我们对于上述图按照之前的算法进行处理完点1,2后,会变成这样
在这里插入图片描述
此时,a={1,2},按照算法,我们应该在剩下的点中寻找入度为0的点,然后我们发现,找不到了,由于有环的存在,我们已经无法在接下来的图中找到入度为0的点了,算法结束,最后序列a定格在a={1,2}无法继续更新。

如果根据上面的算法判断,程序会认为此时的a就是最后的拓扑序列,但是显然不是。我们发现a中的点的数量为2,小于点的总数5。所以,假如我们求出最后的序列中点的数量少于点的总数,那么我们就知道有向图中存在环,该图不存在拓扑序列。

拓扑排序的代码实现

例题链接:Acwing 有向图的拓扑序列

给定一个 n 个点 m 条边的有向图,点的编号是 1 到 n,图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 −1。

若一个由图中所有点构成的序列 A 满足:对于图中的每条边 (x,y),x 在 A 中都出现在 y 之前,则称 A 是该图的一个拓扑序列。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行,每行包含两个整数 x 和 y,表示存在一条从点 x 到点 y 的有向边 (x,y)。

输出格式
共一行,如果存在拓扑序列,则输出任意一个合法的拓扑序列即可。
否则输出 −1。

数据范围
1≤n,m≤1e5
输入样例:
3 3
1 2
2 3
1 3
输出样例:
1 2 3
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

这道题就是一道板子题,所以我们直接贴上代码,不过要看懂代码你需要事先知道以下知识点
1.c++STL中 数据结构queue的基本使用方法
2.链式前向星的存图方法----->链式前向星CSDN博客
3.作者重定义的memset函数( #define mem(a,b) memset(a,b,sizeof(a)) )

//#pragma GCC optimize(2)
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<cstring>
#include<list>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef  pair<int, int> PII;
const int N = 1e5 + 7;
int n, m;
int e[N], ne[N], h[N], id = 1;  //链式前向星存图
int rd[N];  //存放每个点的入度
bool ch[N];  //用来判断该点有没有被放进序列中
bool haveans = true;  //用来判断是否有拓扑序列
queue<int>q;  //用来存放拓扑序列的队列

void add(int a, int b)   //加边的函数
{
	e[id] = b;
	ne[id] = h[a];
	h[a] = id++;
	rd[b]++;
}

void topsort()   //拓扑排序实现函数
{
	bool flag = true;  //flag为true就代表还能找到入度为0的点

	while (flag)
	{
		flag = false;  //先改为,找不到入度为0的点

		for (int i = 1; i <= n; i++)
		{
			if (rd[i] == 0&&!ch[i])
			{
				ch[i] = true;   
				flag = true;   //找到了入度为0的点就把flag改为true,继续循环
				q.push(i);   //把入度为0的点放进队列q
				for (int j = h[i]; j != -1; j = ne[j])    //BFS遍历所有以i为起点的边
				{
					int k = e[j];
					rd[k]--;  //每一条边的入度减一,删除该边
				}
			}
		}

	}

}

void solve()
{
	bool flag = true;
	cin >> n >> m;
	mem(h, -1);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
	}
	topsort();
	if (q.size() != n)   //如果队列中元素数量不等于点的总数就代表图中有环,没有拓扑序列
		cout << "-1" << endl;
	else   //否则输出拓扑序列
		while (!q.empty())
		{
			cout << q.front();
			q.pop();
			if (!q.empty())
				cout << ' ';
			else
				cout << endl;
		}

}

int main()
{
	//std::ios::sync_with_stdio(false);
	//cin.tie(0), cout.tie(0);
	solve();
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99

作者:Avalon Demerzel,喜欢我的博客就点个赞吧,更多图论与数据结构知识点请见作者专栏《图论与数据结构》

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小丑西瓜9/article/detail/64574
推荐阅读
相关标签
  

闽ICP备14008679号