更改

有向无环图 (查看源代码)

2021年5月29日 (六) 16:34的版本

删除1,110字节、 2021年5月29日 (六) 16:34

第221行：第221行： −

Some algorithms become simpler when used on DAGs instead of general graphs, based on the principle of topological ordering. For example, it is possible to find shortest paths and longest paths from a given starting vertex in DAGs in linear time by processing the vertices in a topological order, and calculating the path length for each vertex to be the minimum or maximum length obtained via any of its incoming edges. In contrast, for arbitrary graphs the shortest path may require slower algorithms such as Dijkstra's algorithm or the Bellman–Ford algorithm, and longest paths in arbitrary graphs are NP-hard to find.

−

基于拓扑排序原理，有些算法用在 DAGs 上代替一般图时变得更简单。例如，通过处理拓扑有序中的顶点，并计算每个顶点的路径长度为通过任一传入边得到的最小或最大长度，可以在线性时间内从给定的 DAGs 顶点找到最短路径和最长路径。相反，对于任意图，最短路径可能需要较慢的算法，如 Dijkstra 算法或 Bellman-Ford 算法，而任意图中的最长路径是 np 难以找到的。

=== Topological sorting and recognition ===

第348行：第346行：

反之亦然。也就是说，在任何用有向无环图表示的应用程序中，都存在一个因果结构，要么是例子中显式的顺序或时间，要么是可以从图结构中派生出来的顺序。这是因为所有有向无圈图都有一个拓扑序，即。至少有一种方法可以将顶点按顺序排列，使所有边沿着这个顺序指向同一个方向。

−

== Applications ==

薄荷

7,129

个编辑