拓扑排序

什么是拓扑排序

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

为什么要拓扑排序，假如我们有几个先修课程，有一些没有先修，有些课程之间有先后的关系，有些课程则可以并行的进行，那么我们使用拓扑排序可以得到我们需要修顺序

有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

我们需要如何从一个有向图得到拓扑排序，其实简单，我们只需要循环寻找图中，任意一个没有入度的点，然后把它放到我们拓扑排序中的队列中，然后从图中删除这个点。继续循环寻找。循环直到图为空或找不到入度为0的点，第二种为图有环

另一方法是使用入栈DFS，深度优先搜索的出栈顺序

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。欢迎转载、使用、重新发布，但务必保留文章署名林德熙(包含链接:http://blog.csdn.net/lindexi_gd )，不得用于商业目的，基于本文修改后的作品务必以相同的许可发布。如有任何疑问，请与我联系。

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>