拓扑图的有关知识:
- 广搜的应用
- 针对有向图来说,无向图没有拓扑序列
- 有向无环图一定存在拓扑序列(有向无环图也被称作拓扑图)
- 入度和出度
- 入度为0的点作为拓扑序的起点
- 一个图的拓扑序不一定唯一
过程:
将入度为0的点入队
while(队列不空) {
取出队头t
枚举队头t的所有出边(出边为t -> j)
t的入度--(删除t -> j)
判断t的入度是否为0,若为0则将t加入队列
}
代码
#include
using namespace std;
const int N = 1e5+10;
int n, m, a, b;
int e[N> b,
add (a, b),
d[b] ++; // 统计每个点的入度
if (topsort ()) {
for (int i = 0;i
关注
打赏