387
个编辑
更改
跳到导航
跳到搜索
第64行：
第64行： − +
→拓扑排序和识别
=== 拓扑排序和识别 ===
=== 拓扑排序和识别 ===
{{Main|拓扑排序}}
{{Main|拓扑排序}}
可以用<font color="#ff8000"> '''线性时间复杂度''' </font>的卡恩算法来找到一个有向无环图的拓扑排序。<ref name="clrs">{{Introduction to Algorithms|edition=2}} Section 22.4, Topological sort, pp. 549–552.</ref>简单来说，开设一个存放结果的列表{{mvar|L}}，先将入度为零的节点放到{{mvar|L}}中，因为这些节点没有任何的父节点。将与这些节点相连的边从图中去掉，再寻找图中入度为零的节点。对于新找到的节点来说，他们的父节点已经都在{{mvar|L}}中了，所以也可以从末端插入{{mvar|L}}。重复上述操作，直到找不到入度为零的节点。<ref name="j50" /> 另外一种构造拓扑排序的算法是将[[深度优先搜索]]的[[树的遍历|后序遍历]]结果翻转。<ref name="clrs" />
可以用<font color="#ff8000"> '''线性时间复杂度''' </font>的卡恩算法来找到一个有向无环图的拓扑排序。<ref name="clrs">{{Introduction to Algorithms|edition=2}} Section 22.4, Topological sort, pp. 549–552.</ref>简单来说，开设一个存放结果的列表{{mvar|L}}，先将入度为零的节点放到{{mvar|L}}中，因为这些节点没有任何的父节点。将与这些节点相连的边从图中去掉，再寻找图中入度为零的节点。对于新找到的节点来说，他们的父节点已经都在{{mvar|L}}中了，所以也可以从末端插入{{mvar|L}}。重复上述操作，直到找不到入度为零的节点。<ref name="j50" /> 另外一种构造拓扑排序的算法是将<font color="#ff8000"> '''深度优先搜索''' </font>的<font color="#ff8000"> '''后序遍历''' </font>结果翻转。<ref name="clrs" />
检查一个有向图是否为有向无环图亦可在线性时间内完成。一种方法是先找到一个拓扑排序，然后测试这个排序是否能符合图中每条边所连顶点在排序中应该出现的顺序。<ref>For [[深度优先搜索|depth-first search]] based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g. {{citation|title=The Algorithm Design Manual|first=Steven S.|last=Skiena|publisher=Springer|year=2009|isbn=978-1-84800-070-4|pages=179–181|url=https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA179}}.</ref> 对于卡恩算法在内的部分拓扑排序算法，通过在算法终止时判断是否满足一定条件即可知道图是否有环。<ref name="j50">{{harvtxt|Jungnickel|2012}}, pp. 50–51.</ref>如果有环，卡恩算法最终获得的{{mvar|L}}中节点个数会与图的节点总数不同。
检查一个有向图是否为有向无环图亦可在线性时间内完成。一种方法是先找到一个拓扑排序，然后测试这个排序是否能符合图中每条边所连顶点在排序中应该出现的顺序。<ref>For [[深度优先搜索|depth-first search]] based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g. {{citation|title=The Algorithm Design Manual|first=Steven S.|last=Skiena|publisher=Springer|year=2009|isbn=978-1-84800-070-4|pages=179–181|url=https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA179}}.</ref> 对于卡恩算法在内的部分拓扑排序算法，通过在算法终止时判断是否满足一定条件即可知道图是否有环。<ref name="j50">{{harvtxt|Jungnickel|2012}}, pp. 50–51.</ref>如果有环，卡恩算法最终获得的{{mvar|L}}中节点个数会与图的节点总数不同。