一、拓扑序列的概念
首先明确一点:并不是所有图都有拓扑序列,只有有向无环图具有拓扑序列
看完拓扑序列的概念后大家就能明白这一点
一个图的所有边(x,y),将图中所有节点排成一个序列,保证所有的x都在y前面即为拓扑序列
例如下面这个图:
其中,1 2 3是拓扑序列,因为图中1在2前面,2在3前面
但是1 3 2不是拓扑序列,因为图中2在3前面,但这个序列中3在2前面
也就是说,拓扑序列的顺序一定是按照图中箭头指向的顺序排列的。因此当图中带环时一定无法得出一个拓扑序列,例如:
假设排成1 2 3,但图中3在1前面,序列中1在3前面,不符合拓扑序列的要求,所以有向带环图一定不存在拓扑序列。
因此,有向无环图也被称为拓扑图
二、求有向无环图的拓扑序列
2.1 思想
在这之前,我们首先得明白两个概念
- 入度:指向该节点的边的数量
- 出度:从该节点出发,指向其他节点的边的数量
例如这个图
没有边指向1,有两条边从1出发指向其他节点,因此1的入度为0,出度为2;
有一条边指向2,有两条边从2出发指向其他节点,因此2的入度为1,出度为2;
有三条边指向3,没有边从3出发指向其他节点,因此3的入度为3,出度为0;
有一条边指向4,有一条边从4出发指向其他节点,因此4的入度为1,出度为1
按照拓扑序列的性质,所有入度为0的节点都可以排在拓扑序列的开头,因此这个图的拓扑序列中开头为1
接下来就是求有向无环图的拓扑序列的核心操作:宽搜
第一步,将入度为0的节点入队列
第二步,每次枚举队头节点的所有出边指向的节点,将这些节点的入度减一,再将队头节点出队列。然后回到第一步。
至此,节点的出队顺序1 2 4 3就是该有向无环图的拓扑序列
所以,如果一个有向图带环,则一定存在一个时刻,图中剩余的节点无法入队,因为此时没有入度为0的节点。一个有向图不带环,任意时刻一定至少存在一个节点入度为0
2.2 例题
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int N = 100010;
int n, m;
int e[N], ne[N], h[N], idx;
int d[N];//节点的入度
queue<int> q;
vector<int> ans;
void add(int a,int b) //邻接表
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool topsort()
{
for(int i = 1;i <= n;i++)
if(!d[i]) q.push(i);//将第一个入度为0的节点入队
while(q.size())
{
int t = q.front();//取队头元素
q.pop(); //出队
ans.push_back(t);//元素加入拓扑序列
for(int i = h[t];i != -1;i = ne[i])//遍历所有入边
{
int j = e[i];
d[j]--;//将所有入点的入度-1
if(!d[j]) q.push(j);//将入度为0的节点入队
}
}
return ans.size() == n;//判断拓扑序列的元素个数是否等于节点个数
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 0;i < m;i++)
{
int a, b;
cin >> a >> b;
add(a, b);
d[b]++;//记录入度
}
if(topsort())
{
for(auto i : ans)
cout << i << " ";
cout << endl;
}
else cout << -1 << endl;
return 0;
}
完.