387
个编辑
更改
跳到导航
跳到搜索
第29行：
第29行： − +
→拓扑排序
=== 拓扑排序===
=== 拓扑排序===
[[file:Example_of_a_directed_acyclic_graph.png|thumb|right|175px|图5：一个有向无环图的拓扑排序：每一条边都从排序的前一条（左上）到排序的后一条（右下）。有向图是无环的当且仅当它具有拓扑序]] [[file:Example_of_a_directed_acyclic_graph.png|thumb|right|124px|图6：将红色边添加到蓝色有向无环图中会产生另一个DAG，即蓝色图的传递闭包。对于每个红边或蓝边uv，v可以从u到达：存在一条从u开始到v结束的蓝色路径。]]
[[file:A_topological_ordering_of_a_directed_acyclic_graph.png|thumb|right|175px|图5：一个有向无环图的拓扑排序：每一条边都从排序的前一条（左上）到排序的后一条（右下）。有向图是无环的当且仅当它具有拓扑序]] [[file:Transitive_Closure.svg.png|thumb|right|124px|图6：将红色边添加到蓝色有向无环图中会产生另一个DAG，即蓝色图的传递闭包。对于每个红边或蓝边uv，v可以从u到达：存在一条从u开始到v结束的蓝色路径。]]
有向无环图的<font color="#ff8000"> '''拓扑排序 Topological ordering''' </font>为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。<ref name="bang"/>基于此，拓扑排序可以被用来定义有向无环图：当且仅当一个有向图有拓扑排序，它是有向无环图。一般情况下，拓扑排序并非唯一。有向无环图仅仅在存在一条路径可以包含其所有顶点的情况下，有唯一的拓扑排序方式，这时，拓扑排序与它们在这条路径中出现的顺序相同。<ref>{{citation|title=Algorithms|first1=Robert|last1=Sedgewick|author1-link=Robert Sedgewick (computer scientist)|first2=Kevin|last2=Wayne|edition=4th|publisher=Addison-Wesley|year=2011|isbn=978-0-13-276256-4|url=https://books.google.com/books?id=idUdqdDXqnAC&pg=PA598|pages=598–599|contribution=4,2,25 Unique topological ordering}}.</ref>
有向无环图的<font color="#ff8000"> '''拓扑排序 Topological ordering''' </font>为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。<ref name="bang"/>基于此，拓扑排序可以被用来定义有向无环图：当且仅当一个有向图有拓扑排序，它是有向无环图。一般情况下，拓扑排序并非唯一。有向无环图仅仅在存在一条路径可以包含其所有顶点的情况下，有唯一的拓扑排序方式，这时，拓扑排序与它们在这条路径中出现的顺序相同。<ref>{{citation|title=Algorithms|first1=Robert|last1=Sedgewick|author1-link=Robert Sedgewick (computer scientist)|first2=Kevin|last2=Wayne|edition=4th|publisher=Addison-Wesley|year=2011|isbn=978-0-13-276256-4|url=https://books.google.com/books?id=idUdqdDXqnAC&pg=PA598|pages=598–599|contribution=4,2,25 Unique topological ordering}}.</ref>