《有向无环图及其应用》由会员分享，可在线阅读，更多相关《有向无环图及其应用（19页珍藏版）》请在金锄头文库上搜索。
1、7.1图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题7.5 有向无环图及其应用 7.6 最短路径7.5 有向无环图及其应用7.5.1 有向无环图 有向无环图（directed acycline graph）：无环的有向图，简称DAG 图。DAG图是一类较有向树更一般的特殊有向图。 图7.15 有向树、DAG图和有向图一例例如，图7.15示例了有向树、DAG图和有向图的例子。（2）表达式子式共享例如，下述表达式(a +b ) * (b * (c + d) + (c + d) * e) * (c + d) * e)，用 二叉树表示如图7.16所示，用有向无环图表示如
2、图7.17所示。 图7.16 用二叉树描述表达式*+*+e+*abbccddec d图7.17 描述表达式的有向无环图*+eabc d*+*+*表达式(a +b ) * (b * (c + d) + (c + d) * e) * (c + d) * e)7.5.2 拓扑排序 全序关系：R是集合X上的偏序，若对每个x, yX必有xRy或yRx， 则称R是集合X上的全序关系。（1）定义拓扑排序（Topological Sort）：简单地说，由某个集合上的一个 偏序得到该集合上的一个全序，这个操作称之为拓扑排序。偏序关系：若集合X上的关系R是自反的、反对称的和传递的，则 称R是集合X上的偏序关系。（
3、2）AOV-网AOV-网：用顶点表示活动，用弧表示活动间的优先关系的有向图 称为顶点表示活动的网（Activity On Vertex Network），简称AOV-网。在网中，若从顶点i到顶点j有一条有向路径，则i是j的前驱； j是i的后继。若是网中的一条弧，则i是j的直接前驱； j是i的直接后继。 例如，一个软件专业的学生必须学习一系列基本课程(如图7.18所示)， 其中有些课程是基础课，它独力于其他课程，如高等数学；而另一些 课程必须在学完作为它的基础的先修课程才能开始。如，在程序设计基 础和离散数学学完之前就不能开始学习数据结构。这些先决条 件定义了课程之间的领先（优先）关系。这个关系
4、可以用有向图7.19清楚 的表示。图7.18软件专业的学生必须学习的课程课程编号课程名称先决条件 C1 程序设计基础无 C2 离散数学 C1 C3 数据结构 C1，C2C4 汇编语言 C1C5 语言的设计和分析 C3，C4 C6 计算机原理C11C7 编译原理 C3，C5 C8 操作系统 C3，C6C9 高等数学 无C10 线性代数 C9C12 数值分析 C9，C10，C1C11 普通物理 C9图7.19 表示课程之间优先关系的有向图C4C5C1C2C3C7C12C8 C6C9C10C11图7.19中，顶点表示课程，有向边（弧）表示先决条件。若课程i是 课程j的先决条件，则图中有弧。如下，为图
5、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的顶点即为没有 前驱的顶点，删
6、除顶点及以它为弧的操作，则可换以弧头顶点的入度 减1来实现。Status TopologicalSort (ALGraph G) /有向图G采用邻接表存储结构。 /若G无回路，则输出G的顶点的一个拓扑序列，并返回OK，否则ERROR。 FindInDegree (G, indegree);/对各顶点求入度indegree0vernum1 InitStack (S); for (i = 0; i nextarc) k = padjvex;/对i号顶点的每个邻接点的入度减1 if (!(indegreek) Push (S, k);/若入度减为0，则入栈 / for / while if (cou
7、nt ,之后，只有顶点v1没有前驱，则输出v1且删去v1及弧, 和，之后v3和v4都没有前驱。依次类推，可从中任选一个继续进 行。最后得到该有向图的拓扑有序序列为：。(a)(b)(c)(d)(e)(f)7.5.3 关键路径关键活动：l(i) = e(i)的活动。即活动的最早开始时间最迟开始时间。 显然，关键路径上的所有活动都是关键活动。（1）定义关键路径（Critical Path）：在AOE-网中有些活动可以并行的进行， 所以完成工程的最短时间是从开始点到完成点的最长路径的长度（路径 长度是指路径上各活动持续时间之和，而不是路径上弧的数目）。这个 路径长度最长的路径叫关键路径。AOE-网（A
8、ctivity On Edge）：即边表示活动的网。AOE-网是一个 带权的有向无环图。其中，顶点表示事件（Event），弧表示活动，权 表示活动持续的时间。（2）AOE-网例如，通常，AOE-网可用来估算工程的完成时间。图7.21是一个假想的 有11项活动的AOE-网。其中有9个事件v1, v2, v3, , v9，每个事件表示在它 之前的活动已经完成，在它之后的活动可以开始。与每个活动相联系的数是 执行该活动所需的时间。其中，v1为源点（入度为零的点）；v9为汇点（出度为零的点）。V2V1V3V5V7V4V8V9V6a1=6 a4=1 a7=9 a10=2a2=4 a5=1 a8=7 a1
9、1=4a3=5 a9=4a6=2图7.21 一个AOE-网从vl(n1) = ve(n1)起向后递推vl(i) = Minvl(j)dut() S, i = n2, , 0 其中，S是所有以第i个顶点为尾的弧的集合。（3）事件的最早发生时间ve(j)和最迟发生时间vl(j)从ve(0) = 0开始向前递推ve(j) = Maxve(i) + dut() T, j = 1, 2, , n1 其中，T是所有以第j个顶点为头的弧的集合。dut()是由弧 表示的活动的持续时间。最迟开始时间：在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间。记为l(i)，表示活动ai的最迟开始时间。如果活动
10、ai由弧表示，其持续时间记为dut()，则 e(i) = ve(j) l(i) = vl(k) dut()（4）活动的最早发生时间和最迟发生时间最早开始时间：假设开始点是v1，从v1到vi的最长路径长度叫做事件vi 的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早 开始时间。记为e(i)，表示活动ai的最早开始时间。算法思想： 1输入e条弧，建立AOE-网的存储结构； 2从源点v0出发，令ve0 = 0，按拓扑有序求其余各顶点的最早发生时间vei(1in1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤3。 3从汇
11、点vn出发令vln1 = ven1，按逆拓扑有序求其余各顶点的最迟发生时间veli( 2in2)； 4根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s) = l(s)，则为关键活动。（5）关键路径算法算法实现 如所述，计算各顶点的ve值是在拓扑排序的过程中进行的，需对 拓扑排序的算法作如下修改：1在拓扑排序之前设初值，令vei0(0in1)；2在算法中增加一个计算vj的之间后继vk的最早发生时间的操作： 若ve(j) + dut() vek，则vekve(j) + dut()；3为了能按逆拓扑有序序列的顺序计算各顶点的vl值，需记下在拓
12、扑排序的过程中求得的拓扑有序序列，这需要在拓扑排序算法中，增设 一个栈以记录拓扑有序序列，则在计算求得各顶点的ve值之后，从栈顶至 栈底便为逆拓扑有序序列。Status TopologicalOrder (ALGraph G, Stack /对各顶点求入度indegree0vernum-1 建0入度顶点栈S; InitStack (T); /初始化 count = 0; ve0G.vexnum1 = 0; while (!StackEmpty (S) Pop (S, j);Push (T, j); /j号顶点入T栈并计数+ + count;for (p = G.verticesi.firsta
13、rc; p; p = pnextarc) k = padjvex;/对j号顶点的每个邻接点的入度减1 if (indegreek) = = 0)Push (S, k);/若入度减为0，则入栈算法7.11如下 (由算法7.10改写而成) ：if (vej + * (pinfo) vek)vek = vej + *( pinfo); / for * (pinfo) = dut () / whileif (count nextarc) k = padjvex; dut = *( pinfo);/dut if (vlkdut nextarc) k = padjvex; dut = *( pinfo);
14、 ee = vej; el = vlkdut; tag = (ee = = el) ? * : ; printf (j, k, dut, ee, el, tag);/输出关键活动 / CriticalPath时间复杂度：O(n + e)。例子例如，对图7.22(a)所示的计算结果如图7.23所示，可见a2、a5和a7为关键 活动，组成一条从源点到汇点的关键路径，如图7.22(b)所示。 图7.22 AOE-网及其关键路径(a) AOE-网(b) 关键路径a7=2a4=3V2 V5a1=3 a3=2 a8=1V1 V4 V6a5=4 a2=2 a6=3V3a7a5V1 V4 V6a2V3图7.23 图7.22(a)所示AOE-网中顶点的发生时间和活动开始时间a7 6 6 0顶点vevl 活动 e lle v1 0 0 a1 01 1v
