7,129
个编辑
更改
跳到导航
跳到搜索
第95行：
第95行： + +
→拓扑排序和识别
检查一个有向图是否为有向无环图亦可在线性时间内完成。一种方法是先找到一个拓扑排序，然后测试这个排序是否能符合图中每条边所连顶点在排序中应该出现的顺序。<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">Jungnickel, Dieter (2012), Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics, 5, Springer, pp. 50–51, ISBN 978-3-642-32278-5.</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">Jungnickel, Dieter (2012), Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics, 5, Springer, pp. 50–51, ISBN 978-3-642-32278-5.</ref>如果有环，卡恩算法最终获得的{{mvar|L}}中节点个数会与图的节点总数不同。
<br>
===从其他图构建===
===从其他图构建===