数据结构重读 – 有向无环图、AOV网和拓扑排序

DAG和概念

有向无环图:顾名思义,有向图,且不含环,directed acycline graph,简称DAG图。

无向图检查环:若深度优先遍历过程遇到回边(先前访问过的顶点的边),则必定存在环。

有向图检查环:从某个顶点v出发,在dfs(v)结束前,出现一条从顶点u到顶点v的回边,由于u在生成树上是v的子孙,则有向图必定存在包含顶点v和u之间的环。

DAG图是描述工程的有效工具。一个工程可以用一个DAG图表示,每一个顶点是一个子工程,工程的先后关系用弧表示。

围绕着工程,两个关心的问题是:

1、工程能否顺利进行(拓扑排序问题)

2、工程完成所必须的最短时间(关键路径问题)

 

AOV网和拓扑排序

偏序:集合中仅有部分成员之间可以比较。

全序:集合中全体成员均可比较。

比如下图左边是偏序,右边是全序。

拓扑有序:全序上面的排序

拓扑排序:由于集合上一个偏序得到该集合上的一个全序。

AOV网(Activity On Vertex Network):用顶点表示活动,用弧表示活动之间的优先关系的有向图称为顶点表示活动的网。

在AOV网上不应该出现有向环,因此,给定一个AOV网,要先判断是否存在环。

AOV图求拓扑排序的算法如下

1、从有向图中选取一个没有前驱的顶点(入度为0的)。

2、从图中删除该顶点和所有以它为尾的弧(此时可能会产生新的无前驱顶点)。

循环上述两步,直到

(1)所有顶点都全部输出。

Or

(2)不存在无前驱的顶点,说明图中有环。

上述算法非常简单明了,连AOV图的环判定也一起做了。

具体到实现,我们可以增添两个数据结构:

(1) 存放各个顶点入度的集合indegree。

(2)一个暂存入度为0的栈。

算法变成了:

1、扫描所有顶点的入度。

2、将入度为0的,入栈。

3、循环直到栈空

弹出栈、输出。

将关联的边入度减1,如果为0,入栈。

4、最终检查输出了多少个结点,如果小于nvexs,说明有环。

代码如下:

注意这里是有向图,图的创建不能在用无向图的双边了!

测试的AVO图:

测试数据:

测试输出:

6  1  4  3  5  2

 

 

 

 

Leave a Reply

Your email address will not be published.