图论-拓扑排序详解图论-拓扑排序详解

拓扑排序（topsort）详解这篇随笔就信息学奥林匹克竞赛中图论的一个知识点——拓扑排序进行讲解。拓扑排序的内容比较基础，只要求读者学习过并了解信息学中图的相关定义和一些专业名词，但是拓扑排序的变形题目比较多，希望读者在看完本随笔后认真体会练习，掌握拓扑排序。
上课！拓扑排序的定义顾名思义，这是一种排序，确切地说，是一种图上排序，在一张有向无环图（注解：有向无环图即很多参考书和题解中所说的DAG）上进行排序，把其中的所有节点排成一个序列，使得图中的任意一对有边相连的节点（u,v）u要出现在v前。
所以我再次强调，拓扑排序只能用在有向无环图中！！
这样的线性序列我们称之为拓扑序。
注意，拓扑序不唯一！这个地方不明白的请自己画图理解（或者参考下面的那棵树）。
拓扑排序的实现原理在讲解图的拓扑排序之前，我们可以用一棵树来加深对拓扑排序的理解（因为树是绝对没有环）。
我们随意地定义一棵有向树（如下图），如果我们想得到它的拓扑序，那会很简单，只需要先把根节点8号放进队列中，然后再放8号的任意一个儿子节点，继续此操作。直到节点全放进去为止。

文章图片

我们会发现，问放进去的是任意的一个子节点，所以我们说拓扑序是不唯一的（在绝大多数情况下，你要非跟我抬杠说假如只有一条链，我也没办法）。
拓扑排序的实现讲完了实现原理，我们来进行拓扑排序的代码实现，根据上面的原理，我们会发现，我们要保证拓扑序列的正确性，只需要把图中的入度为0的节点先放进拓扑序，然后把这个点和它所有的出边全部删掉，这样就还会出现一些入度为0的点，我们继续重复以上操作。
有细心的小伙伴会发现这个和算法中的宽搜很相似，没错，所谓宽搜和深搜，都是基于对树与图的深度/宽度优先遍历而定义的，所以拓扑排序的实现其实就是借助了宽搜的思想。
上模板：

void topsort() { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(rudu[j]==0) { x=j; top[++cnt]=j; rudu[j]--; break; } } for(int j=head[x]; j; j=nxt[j]) rudu[j]--; } }

以上代码的top数组存拓扑序列，使用的是链式前向星存图并遍历。比较好理解，但是时间复杂度比较低。（所以仅供理解）
所以我们用C++STL来实现拓扑排序，这样会快很多。
模板：

void topsort() { queue q; for(int i=1; i<=n; i++) if(rudu[i]==0) q.push(i); while(q.empty()) { int x=q.front(); q.pop(); top[++cnt]=x; for(int i=head[x]; i; i=nxt[i]) { int y=to[i]; rudu[y]--; if(rudu[y]==0) q.push(y); } } }

其实也很好理解啦...
注意，以上代码是针对于已经保证图是DAG的情况下而出现的，假如我们没有题目中DAG的保证，就要额外地判这个图是不是DAG，即很多题目中要求的“无解”情况。
怎么判断呢？
学到这里，我觉得你应该想到，如果最后得到的拓扑序列的长度等于节点总数，那么这个图就是DAG，否则就不是。
所以我们最后进行判断。
（你也可以使用STL中的vector容器）
代码：

if(cnt==n) //DAG操作 else //非DAG操作

拓扑排序的用途及一些技巧拓扑排序的用途是解决一些依赖关系的题，一般来讲没有图论的基本要素（告诉你几个点，一眼就看出来这是一道图论题%%%），所以，我认为做拓扑排序题的难点在于如何建立一个和题意相符的图（建图坑死爹）。所以美其名曰拓扑排序是图论中最简单的内容，其实它的相关题目都很有思维含量，所以强烈建议各位同学~~多刷题多刷题~~。
由于拓扑排序不唯一，所以有些坑爹题目要求拓扑序列的一些内容，比如按字典序等等。
这时我们把原本的队列拓扑排序换成优先队列拓扑排序。
注意，优先队列不能提速，不要以为找到了一份更好的模板，一定要读题~~！！
除了定义方式有点怪异其他的跟队列一样。