387
个编辑
更改
跳到导航
跳到搜索
第166行：
第166行： − + − + − 拓扑排序是寻找给定 DAG 的拓扑顺序的计算问题。它可以在线性时间内求解。的拓扑排序算法直接建立顶点排序。它维护了一个顶点列表，这些顶点没有来自其他没有被部分构造的拓扑顺序包括在内的顶点的入射边; 最初这个列表由没有入射边的顶点组成。然后，它重复地从这个列表中添加一个顶点到部分构造的拓扑排序的末尾，并检查它的邻居是否应该添加到这个列表中。当所有顶点都以这种方式被处理时，算法终止。或者，对于某些拓扑排序算法，通过验证算法成功地排序所有顶点，而不满足错误条件。+ + + + +
→Topological sorting and recognition
== Computational problems ==
== Computational problems ==
=== Topological sorting and recognition ===
=== Topological sorting and recognition 拓扑排序和识别 ===
Topological sorting is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in linear time. Kahn's algorithm for topological sorting builds the vertex ordering directly. It maintains a list of vertices that have no incoming edges from other vertices that have not already been included in the partially constructed topological ordering; initially this list consists of the vertices with no incoming edges at all. Then, it repeatedly adds one vertex from this list to the end of the partially constructed topological ordering, and checks whether its neighbors should be added to the list. The algorithm terminates when all vertices have been processed in this way. or alternatively, for some topological sorting algorithms, by verifying that the algorithm successfully orders all the vertices without meeting an error condition.
Topological sorting is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in linear time.[16] Kahn's algorithm for topological sorting builds the vertex ordering directly. It maintains a list of vertices that have no incoming edges from other vertices that have not already been included in the partially constructed topological ordering; initially this list consists of the vertices with no incoming edges at all. Then, it repeatedly adds one vertex from this list to the end of the partially constructed topological ordering, and checks whether its neighbors should be added to the list. The algorithm terminates when all vertices have been processed in this way.[17] Alternatively, a topological ordering may be constructed by reversing a postorder numbering of a depth-first search graph traversal.[16]
可以用线性时间复杂度的卡恩算法来找到一个有向无环图的拓扑排序。[17]简单来说，开设一个存放结果的列表L，先将入度为零的节点放到L中，因为这些节点没有任何的父节点。将与这些节点相连的边从图中去掉，再寻找图中入度为零的节点。对于新找到的节点来说，他们的父节点已经都在L中了，所以也可以从末端插入L。重复上述操作，直到找不到入度为零的节点。[17] 另外一种构造拓扑排序的算法是将深度优先搜索的后序遍历结果翻转。[16]
It is also possible to check whether a given directed graph is a DAG in linear time, either by attempting to find a topological ordering and then testing for each edge whether the resulting ordering is valid[18] or alternatively, for some topological sorting algorithms, by verifying that the algorithm successfully orders all the vertices without meeting an error condition.[17]
检查一个有向图是否为有向无环图亦可在线性时间内完成。一种方法是先找到一个拓扑排序，然后测试这个排序是否能符合图中每条边所连顶点在排序中应该出现的顺序。[18] 对于卡恩算法在内的部分拓扑排序算法，通过在算法终止时判断是否满足一定条件即可知道图是否有环。[17]如果有环，卡恩算法最终获得的L中节点个数会与图的节点总数不同。
=== Construction from cyclic graphs ===
=== Construction from cyclic graphs ===