图的遍历——拓扑排序

背景知识

拓扑排序就是对有向无环图，将所有顶点排成一个线性序列，该序列满足：如果图里有边$<u,v>$，那么在该序列里，u一定要在v前面

算法思想

1. 找到入度为0的点（有向无环图中必定存在！），挨个输出（可能不止一个）
2. 删除这些入度为0的点，并且删除以这些点为起点的边
3. 这样又会出现新的一波入度为0点，输出！
4. 然后重复操作，直到没有点了为止

实现思路

1. 找入度为0点，可以搞个数组，如果用链式前向星存
2. 删掉边的目的就是为了减小入度，直接对入度数组操作
3. 对于找到的点，我们可以放到一个数组里
4. 点变多，所以数组它应该不断变大，就得有个东西记录它的个数（已经排序的个数）
5. 处理一个点的边，就可以判断一下该边终点

代码实现

int que[maxn];
int iq=0;
for(int i=1;i<=n;i++)
{
if(indegree[i]==0)
que[iq++]=i;
}
for(int i=0;i<iq;i++)
{
for(int j=head[que[i]];j!=-1;j=edge[k].next)
{
indegree[edge[j].to]--;
if(indegree[edge[j].to]==0)
{
que[iq++]=edge[k].to;
}
}
}
for(int i=0;i<iq;i++)
cout<<que[i]<<" ";

• 时间复杂度：$O(n+m)$

补充

• 要是找不到，呢个记录数组长度的小于n
• 拓扑序列不止一个
• 想输出所有的，就深搜吧

最后

以上就是文静盼望为你收集整理的图的遍历——拓扑排序的全部内容，希望文章能够帮你解决图的遍历——拓扑排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。