发布网友
发布时间：2022-04-21 23:45
共1个回答
热心网友
时间：2023-11-17 06:39
有向无回路图又称为dag。对这种有向无回路图的拓扑排序的结果为该图所有顶点的一个线性序列，满足如果G包含(u,v)，则在序列中u出现在v之前（如果图是有回路的就不可能存在这样的线性序列）。一个图的拓扑排序可以看成是图的所有顶点沿水平线排成的一个序列，使得所有的有向边均从左指向右。因此，拓扑排序不同于通常意义上对于线性表的排序。
有向无回路图经常用于说明事件发生的先后次序，图1给出一个实例说明早晨穿衣的过程。必须先穿某一衣物才能再穿其他衣物（如先穿袜子后穿鞋），也有一些衣物可以按任意次序穿戴（如袜子和短裤）。
图中说明经拓扑排序的结点以与其完成时刻相反的顺序出现。因为深度优先搜索的运行时间为θ(V+E)，每一个v中结点插入链表需占用的时间为θ(1)，因此进行拓扑排序的运行时间θ(V+E)。
为了证明算法的正确性，我们运用了下面有关有向无回路图的重要引理。 有向图G无回路当且仅当对G进行深度优先搜索没有得到反向边。
证明：→：假设有一条反向边(u,v)，那么在深度优先森林中结点v必为结点u的祖先，因此G中从v到u必存在一通路，这一通路和边(u,v)构成一个回路。
←：假设G中包含一回路C，我们证明对G的深度优先搜索将产生一条反向边。设v是回路C中第一个被发现的结点且边(u,v)是C中的优先边，在时刻d[v]从v到u存在一条由白色结点组成的通路，根据白色路径定理可知在深度优先森林中结点u必是结点v的后裔，因而(u,v)是一条反向边。（证毕） Topological_Sort(G)算法可产生有向无回路图G的拓扑排序
证明
假设对一已知有问无回路图G=(V,E)运行过程DFS以确定其结点的完成时刻。那么只要证明对任一对不同结点u,v∈V，若G中存在一条从u到v的有向边，则f[v]<F[U]即可。考虑过程DFS(G)所探寻的任何边(U,V)，当探寻到该边时，结点V不可能为灰色，否则V将成为U的祖先，(U,V)将是一条反向边，和引理1矛盾。
因此，v必定是白色或黑色结点。若v是白色，它就成为u的后裔，因此f[v]<F[U]。若V是黑色，同样F[V]<F[U]。这样一来对于图中任意边(U,V)，都有F[V]<F[U]，从而定理得证。（证毕）
Copyright © 2019-2022 51dongshi.com 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
