《第7章图2.ppt

第7章 图 学习要点: 熟悉图的各种存储结构及其构造算法 了解实际问题的求解效率与采用何种存储结构和算法有密切联系 熟练掌握图的两种有哪些信誉好的足球投注网站路径的遍历：深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站 应用图的遍历算法求解各种简单路径问题，如关键路径、最短路径等 7.5 有向无环图及其应用 定义： 一个无环的有向图称作有向无环图(Directed Acycline Graph)，简称DAG图。 有向无环图是描述含有公共子式的表达式的有效工具。如对下述表达式： ((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e) 可以用二叉树来表示。 有向无环图也是描述一项工程或系统的进行过程的有效工具。 绝大多数的工程都可分为若干个活动的子工程，而这些子工程之间，通常都受着一定条件的约束。 对整个工程和系统，人们关心的是两个方面的问题： 一是工程能否顺利进行； 二是工程完成所必须的最短时间。 对应于有向图，即为进行拓扑排序和求关键路径的操作。 7.5.1 拓扑排序 问题： 假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。 检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。 何谓“拓扑排序”？ 对有向图进行如下操作： 按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。 由此所得顶点的线性序列称之为拓扑有序序列。 例如：对于下列有向图。 可求得拓扑有序序列：A B C D 或 A C B D 反之，对于下列有向图： 不能求得它的拓扑有序序列，因为图中存在一个回路 {B, C, D} 用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network)，简称AOV-网。 在AOV-网中不应该出现有向环。 对给定的AOV-网需首先判断网中是否有环。 例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。(见下表) 检测是否有环的办法： 对有向图构造其顶点的拓扑有序序列； 若网中所有顶点都在其拓扑有序序列中，则该AOV-网必定不存在环。 如何进行拓扑排序？ 从有向图中选取一个没有前驱的顶点，并输出之； 从有向图中删去此顶点以及所有以它为尾的弧； 重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。 例如： 在算法中需要用定量的描述替代定性的概念： 没有前驱的顶点 ?? 入度为零的顶点； 删除顶点及以它为尾的弧 ?? 弧头顶点的入度减1。 算法描述： 取入度为零的顶点v; while (v0) { printf(v); ++m; w:=FirstAdj(v); while (w0) { inDegree[w]--; w:=nextAdj(v,w); } 取下一个入度为零的顶点v; } if mn printf(“图中有回路”); 为避免每次都要有哪些信誉好的足球投注网站入度为零的顶点，在算法中设置一个“栈”，以保存“入度为零”的顶点。 CountInDegree(G,indegree); //对各顶点求入度 InitStack(S); for ( i=0; iG.vexnum; ++i) if (!indegree[i]) Push(S, i); //入度为零的顶点入栈 count=0; //对输出顶点计数 while (!EmptyStack(S)) { Pop(S, v); ++count; printf(v); for (w=FirstAdj(v); w; w=NextAdj(G,v,w)){ --indegree(w); // 弧头顶点的入度减一 if (!indegree[w]) Push(S, w); //新产生的入度为零的顶点入栈 } } if (countG.vexnum) printf(“图中有回路”); 7.5.2 关键路径 问题： 假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。问：哪些子工程项是“关键工程”？即：哪些子工程项将影响整个工程的完成期限的。 整个工程完成的时间为：从有向图的源点到汇点的最长路径。 AOE-网：边表示活动的网。如上图， 顶点表示事件、弧表示活动、权表示活动持续的时间。 用AOE-网可估算工程的完成时间。对AOE网，常考虑如下的情况： 完成整个工程至少需要多少时间？ 哪些活动是影响工程进度的关键？