• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

DAG,AOV,AOE和拓扑排序

开发技术 开发技术 2周前 (04-30) 4次浏览

DAG(Directed Acyclic Graph简称DAG),就是有向无环图,DAG这种图中的所有边都是有向边,而且从任意一个顶点开始,都找不到回到起始点的环路。
例子也不免俗的举一个:
DAG,AOV,AOE和拓扑排序

我们可以对某些,记住是某些DAG图进行排序:拓扑排序,记住,是某些图。
至于为什么要排序(或者说排序有什么用),网上很多资料都有解释(比如要自学某一个课程,可能要首先自学其他很多门必备的基础课程,拓扑排序可以安排你的学习流程),不再赘述。
所谓拓扑排序,就是把DAG图按照次序输出,并且保证输出序列的次序和顶点之间的先后次序一致。很熟悉的感觉吧。让我们想起了有向图的遍历,其实有向图的深度和广度遍历都是一次拓扑排序。
我们知道,遍历的开始节点可以任意选,但是拓扑排序的起始节点则不能任意选,比如,上面的图中,我们不能选节点7意外的节点开始排序,这将导致节点7的前驱节点排在节点7之后。
同时,因为选择起始节点可能不同,还有算法也可能不同(比如深度排序排序时候选下一个节点的的nextNBr函数的结果不同),拓扑排序的结果也必然不是唯一的。
从上面的讨论我们也可以得出:一个可以进行拓扑排序的DAG图的基本特征,必然存在至少一个入度为0的节点,如此才可以排序.

其实,上面我们讨论的,符合一定条件的图就是AOV网(Active on vertices):用顶点表示活动的网络。
此处补充说明一下,数据结构中,好像大部分教材将网定义为:边具有权重的图。而有的书则说:有向图就是网。从AOV的特征,排序不涉及边的权重,因此对于网的定义,需要再次查找资料确认。

DAG的另一个应用就是AOE网。
AOE和AOV名字相近,含义却不一样(其实什么含义都是认为赋予的),AOE:就是Active on Edges,用边表示活动的网。既然名字这么规定,说明边有特殊性,比如边的权重参数能就比较重要,举例来说:
比如我们要做饭,从开始那一刻,就要处理很多事情(事件),而每一个事件,都要花费时间。这里,用顶点表示事件开始,用边表示处理这个事件所花费的时间(当然,地图导航也符合AOE的性质),而且,我们在烧水的时候,还可以同时洗菜,切菜等事件和过程,这些时间和过程,用顶点,边来描述,就是一个有AOE网,最终我们会用这个AOE网络计算出:饭菜做好至少需要多久。看下图:


程序员灯塔
转载请注明原文链接:DAG,AOV,AOE和拓扑排序
喜欢 (0)