Topological sort 又称 Topological order，这个名字有点迷惑性，因为拓扑排序并不是一个纯粹的排序算法，它只是针对某一类图，找到一个可以执行的线性顺序。

这个算法听起来高大上，如今的面试也很爱考，比如当时我在面我司时有整整一轮是基于拓扑排序的设计。

但它其实是一个很好理解的算法，跟着我的思路，让你再也不会忘记她。

有向无环图

刚刚我们提到，拓扑排序只是针对特定的一类图，那么是针对哪类图的呢？

答：Directed acyclic graph (DAG)，有向无环图。即：

1. 这个图的边必须是有方向的；
2. 图内无环。

那么什么是方向呢？

比如微信好友就是有向的，你加了他好友他可能把你删了你却不知道。。。那这个朋友关系就是单向的。。

什么是环？环是和方向有关的，从一个点出发能回到自己，这是环。

所以下图左边不是环，右边是。

那么如果一个图里有环，比如右图，想执行1就要先执行3，想执行3就要先执行2，想执行2就要先执行1，这成了个死循环，无法找到正确的打开方式，所以找不到它的一个拓扑序。

总结：

• 如果这个图不是 DAG，那么它是没有拓扑序的；
• 如果是 DAG，那么它至少有一个拓扑序；
• 反之，如果它存在一个拓扑序，那么这个图必定是 DGA.

所以这是一个充分必要条件。