图的拓扑排序

81 阅读 0 评论 54 点赞

我是靠谱客的博主多情背包，这篇文章主要介绍图的拓扑排序，现在分享给大家，希望可以做个参考。

图的拓扑排序是图的宽度优先遍历的一个应用
针对有向无环图；
都是由前指向后，有向无环图一定存在拓扑序列，所以也被称为拓扑图
一个有向无环图，一定至少有一个入度为0的点；

要进行拓扑排序，思路很简单：

入度：指向它的路径个数

出度：从它指出去的路径个数

1.以入度为零的点为突破口，将其入队

2.遍历这个点指向的所有下一个点，再将下一个点的入度减一。

3.不断重复1.2的操作，直至结束
ps：用队列存储这些入度为零的点，遍历完毕的点出队，入度为零的点入队，邻接表存储路径。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool topsort()
{
	int hh==0;tt=-1;
	for(int i=1;i<=n;i++)
	{
		if(!d[i])
		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]--;//j的入度-1
			if(d[j]==0) q[++tt]=j;//当入度为零时，j入队
		}
	 } 
	 return tt==n-1;
}