图之拓扑排序与最短路径的引入

2017年2月26日 9点热度 0条评论 来源: 逐鹿之城

一.有向无环图
1.Directed Acircline Graph,即一个无环的有向图,它是描述含有公共子式表达式的有效工具,可以实现共享相同子式,节省存储空间。
例如:对于下面的表达式分别用二叉树描述和有向无环图描述


2.有向图无环的判断

二.拓扑排序与最短路径的引入
一个工程,往往会分成几个阶段,某些子工程的开始必须建立在一些子工程已经完成的基础之上,这影响着工程是否能够顺利进行。对整个工程和系统,人们最关心两个问题:1.工程是否能顺利进行。2.估算整个工程完成的最短时间。这对应于有向图,分别是拓扑排序和求最短路径。

三.AOV与AOE
AOV-网即顶点为活动的网,AOE-网即边为活动的网(或者边上的权重)。在AOV网中,我们关注的顶点;在AOE中,关注的是边。举个例子,一个排课系统,关注的是每一门课,所以这就是一个AOV-网。从一个城市到另一个城市的旅游路程规划,关注的是路上的花费或者旅行所需要的时间,这就是一个AOE-网。在一个工程中,被细分出的每一个小工程构成一个AOV网络,AOE网络用来估算整个工程花费的时间。
在有向图中,AOV-网用来进行拓扑排序,AOE-网用来进行最短路径的求解
在AOV-网中,不应出现有向环,因为有向环意味着某项活动应以自己为先决条件。显然,这很荒谬。设计出这样的流程图,则工程无法进行。而对程序的数据流图来说,则是一个死循环。因此,对给定的AOV-网应该首先判断是否有环。这在下一篇中给出思路和代码实现

    原文作者:逐鹿之城
    原文地址: https://blog.csdn.net/derkampf/article/details/57414185
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。