图的拓扑排序

56 阅读 0 评论 37 点赞

我是靠谱客的博主多情背包，最近开发中收集的这篇文章主要介绍图的拓扑排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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

入度：指向它的路径个数

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

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

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

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

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;
}

我们可以发现，在进行拓扑排序操作时，入度为0的顶点不一定唯一，可以从中随机选择；这意味着拓扑排序的结果不一定是唯一的。