有向图的拓扑序列
就是图的宽度优先遍历的应用
无向图没有拓扑序列。
题意理解
给定一个 n 个点 m 条边的有向图,点的编号是 1 到 n,图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 −1。
若一个由图中所有点构成的序列 A 满足:对于图中的每条边 (x,y),x 在 A 中都出现在 y 之前,则称 A 是该图的一个拓扑序列。
举例说明:
可以证明有向无环图一定存在一个拓扑序列!所以有向无环图又被称为拓扑图
入度、出度
入度、出度是针对点来说的。
一个点的入度:有多少个点指向自己
一个点的出度:指向多少个点
如图:
则可以根据入度、出度进行拓扑排序。
入度为0
:没有被任何一条边指向,它可以排在最前面作为起点。
// 拓扑排序伪代码
// d[]表示入度
queue <- 所有入度为0的点 // 把所有入度为0的点入队
while queue 不空
{
t <- 队头 // 取出队头
枚举t的所有出边 t -> j
删掉 t -> j, d[j] -- ; // t已经排到最前面,j一定在t的后面。删掉指向j的边,j的入度-1
if (d[j] == 0)
queue <- j
}
一个有向无环图一定至少存在一个入度为0的点。
代码如下
邻接表参考题解:树的重心
链表模拟队列参考题解:模拟队列
树的宽度优先遍历:图中点的层次
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx; // 数组模拟邻接表!h[]存储每个节点链表的头节点
int q[N], d[N]; // q[]表示队列,d[]表示入度
void add(int a, int b) // 给图添加一条边,用邻接表存储
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool topsort() // 判断是否是拓扑序列,链表模拟队列
{
int hh = 0, tt = -1; // 队头队尾
for (int i = 1; i <= n; i ++ )
if (!d[i]) // 如果入度等于0,将这个节点加入队列
q[ ++ tt] = i;
while (hh <= tt) // 队列不空
{
int t = q[hh ++ ]; // 取出队头
for (int i = h[t]; i != -1; i = ne[i]) // 遍历邻接表
{
int j = e[i]; // 取出出边
d[j] -- ; // 入度-1
if (d[j] == 0) q[ ++ tt] = j; // 如果入度等于0,将这个节点加入队列
}
}
return tt == n - 1; // 如果队列长度等于所有点的个数。(所有点都加入队列)
}
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] ++ ; // a->b,把b的入度+1
}
if (topsort()) // 如果满足拓扑序,输出
{
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
puts("");
}
else puts("-1");
return 0;
}
拓扑序列可能不唯一