有向无环图及其应用.ppt

7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径￡7.5有向无环图及其应用￡7.5.1有向无环图有向无环图（directedacyclinegraph）：无环的有向图，简称DAG图。DAG图是一类较有向树更一般的特殊有向图。图7.15有向树、DAG图和有向图一例例如，图7.15示例了有向树、DAG图和有向图的例子。（2）表达式子式共享例如，下述表达式((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)，用二叉树表示如图7.16所示，用有向无环图表示如图7.17所示。图7.16 用二叉树描述表达式*+***+e+++*abbccddecd图7.17 描述表达式的有向无环图*+eabcd*+*+*表达式((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)￡7.5.2拓扑排序全序关系：R是集合X上的偏序，若对每个x,y∈X必有xRy或yRx，则称R是集合X上的全序关系。（1）定义拓扑排序（TopologicalSort）：简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。偏序关系：若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。 （2）AOV-网AOV-网：用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网（ActivityOnVertexNetwork），简称AOV-网。在网中，若从顶点i到顶点j有一条有向路径，则i是j的前驱；j是i的后继。若i,j是网中的一条弧，则i是j的直接前驱；j是i的直接后继。例如，一个软件专业的学生必须学习一系列基本课程(如图7.18所示)，其中有些课程是基础课，它独力于其他课程，如《高等数学》；而另一些课程必须在学完作为它的基础的先修课程才能开始。如，在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先（优先）关系。这个关系可以用有向图7.19清楚的表示。图7.18 软件专业的学生必须学习的课程课程编号 课程名称 先决条件C1 程序设计基础 无C2 离散数学 C1C3 数据结构 C1，C2C4 汇编语言 C1C5 语言的设计和分析 C3，C4C6 计算机原理 C11C7 编译原理 C3，C5C8 操作系统 C3，C6C9 高等数学 无C10 线性代数 C9C12 数值分析 C9，C10，C1C11 普通物理 C9图7.19表示课程之间优先关系的有向图C4C5C1C2C3C7C12C8C6C9C10C11图7.19中，顶点表示课程，有向边（弧）表示先决条件。若课程i是课程j的先决条件，则图中有弧i,j。如下，为图7.19中的有向图的拓扑有序序列的其中两个序列： 1．(C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8) 2．(C9,C10,C11,C6,C1,C12,C4,C2,C3,C5,C7,C8)（3）拓扑排序①算法思想： 1．在有向图中选一个没有前驱的顶点且输出之。 2．从图中删除该顶点和所有以它为尾的弧。 3．重复上述两步，直至全部顶点均已输出，或者当前图中步存在无前驱的顶点为止。②算法实现：针对上述操作，采用邻接表作有向图的存储结构，且在头结点中增加一个存放顶点入度的数组（indegree）。入度为0的顶点即为没有前驱的顶点，删除顶点及以它为弧的操