知识点回顾 生成树、生成森林 概念、生成过程 最小生成树 概念、 MST 性质 普里姆算法和克鲁斯卡尔算法.

Presentation on theme: "知识点回顾 生成树、生成森林 概念、生成过程 最小生成树 概念、 MST 性质 普里姆算法和克鲁斯卡尔算法."— Presentation transcript:

1 知识点回顾 生成树、生成森林 概念、生成过程 最小生成树 概念、 MST 性质 普里姆算法和克鲁斯卡尔算法

2 第六章 图 6.1 图的定义和术语 6.2 图的存储结构 6.3 图的遍历 6.4 图的连通性问题 6.5 有向无环图及其应用
6.6 最短路径

3 6.5 有向无环图及其应用 一个无环的有向图叫做有向无环图(directed acycline graph),简称DAG图
判断有向图中是否存在环的方法 有向图 有向树 DAG图

4 6.5.1 拓扑排序 问题提出：学生选修课程问题 顶点——表示课程 有向弧——表示先决条件，若课程i是课程j的先决条件，则图中有弧<i,j> 学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业——拓扑排序 定义 AOV网——用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网 若<vi,vj>是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继 AOV网中不允许有回路，这意味着某项活动以自己为先决条件，即若AOV网中存在有向环，该AOV网所代表的工程是不可行的

5 在图中，我们用一种有向图来表示课程开设 例 课程代号 课程名称 先修课 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11
课程代号 课程名称 先修课 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 无 C1,C2 C3,C4 C3.C5 C3,C6 C1,C9,C10 程序设计基础 离散数学 数据结构 汇编语言 语言的设计和分析 计算机原理 编译原理 操作系统 高等数学 线性代数 普通物理 数值分析 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 在图中，我们用一种有向图来表示课程开设

6 6.5.1 拓扑排序 拓扑排序——把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫~
检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环 拓扑序列的实际意义: 如果按照拓扑序列中的顶点次序进行每一项活动,就能够保证在开始每一项活动时,他的所有前驱活动均已完成,从而使整个工程顺序执行。

7 6.5.1 拓扑排序 拓扑排序的方法 在AOV网中选一个没有前驱的顶点且输出之 从AOV网中删除该顶点和所有以它为尾的弧

8 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8 或 ：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8 一个AOV网的拓扑序列不是唯一的

9 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12

10 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1 （1） C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1--C2 （2）

11 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1--C2--C3 （3） C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1--C2--C3--C4 （4）

12 C6 C7 C8 C9 C10 C11 C12 拓扑序列：C1--C2--C3--C4--C5 （5） C6 C8 C9 C10 C11 C12 拓扑序列：C1--C2--C3--C4--C5--C7 （6） C6 C8 C11 C12 拓扑序列：C1--C2--C3--C4--C5--C7--C9 --C10 （8） C6 C8 C10 C11 C12 拓扑序列：C1--C2--C3--C4--C5--C7--C9

13 C8 C12 拓扑序列：C1--C2--C3--C4--C5--C7--C9 --C10--C11--C6 （10） C6 C8 C12 拓扑序列：C1--C2--C3--C4--C5--C7--C9 --C10--C11 （9） C8 拓扑序列：C1--C2--C3--C4--C5--C7--C9 --C10--C11--C6--C12 （11） 拓扑序列：C1--C2--C3--C4--C5--C7--C9 --C10--C11--C6--C12--C8 （12）

14 6.5.1 拓扑排序 AOV网的存储：邻接表 为每个顶点设立一个链表,每个链表的头指针构成一个顺序表,顺序表中得每个结点都增加一个存放顶点入度的字段. 1 2 in link 5 4 3 ^ vex next 6 例 1 2 3 4 5 6 邻接表的产生：在输入有向图的边之前,每个链表的头指针都置为空,入度置为零。每输入一条有向边时，在第i个链表中，建立一个顶点为j的边结点，同时将顶点j的入度加1。

15 6.5.1 拓扑排序 拓扑排序的算法步骤 在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后续顶点的入度减1，为了避免重复检测入度为零的顶点，设立一个栈，以存放入度为零的顶点。执行拓扑排序的算法步骤如下：

16 算法实现 以邻接表作存储结构 把邻接表中所有入度为0的顶点进栈
栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈 重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕 表头结点： typedef struct tnode { int in; //入度域 struct node *link; //链域 }TD; TD g[M]; //g[0]不用 邻接表结点： typedef struct node { int vex; //顶点域 struct node *next;//链域 }JD;

17 1 2 in link 5 4 3 ^ vex next 6 例 1 2 3 4 5 6 3 2 1 4 top top 6 top 1

18 in link 5 4 3 ^ vex next 2 1 6 p=NULL 3 2 1 4 输出序列： top

19 6.5.1 拓扑排序 拓扑排序算法的时间复杂度分析 如果给定的有向图有n个顶点和e条边，那么建立邻接表的时间为O（e），在拓扑排序的过程中，查找入度为零的顶点的时间为O（n），顶点进栈及退栈输出共执行n次，入度减1的操作执行e次，所以，总的执行时间为O（e+n）。

20 6.5.2 关键路径 问题提出 把工程计划表示为有向图，用顶点表示事件，弧表示活动；
关键路径 问题提出 把工程计划表示为有向图，用顶点表示事件，弧表示活动； 每个事件表示在它之前的活动已完成，在它之后的活动可以开始 例 设一个工程有11项活动，9个事件 事件 V1——表示整个工程开始 事件V9——表示整个工程结束 问题：（1）完成整项工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键？

21 关键路径 定义 AOE网(Activity On Edge)——也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间 注意： AOE网中只有一个入度为0的源点和一个出度为0的汇点。 9 8 7 6 4 5 3 2 1 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 AOE-网

22 6.5.2 关键路径 路径长度——路径上各活动持续时间之和 关键路径——路径长度最长的路径叫~ Ve(j)——表示事件Vj的最早发生时间
关键路径 路径长度——路径上各活动持续时间之和 关键路径——路径长度最长的路径叫~ Ve(j)——表示事件Vj的最早发生时间 ve(i) = 从源点V1到顶点Vi的最长路径长度; Vl(i)——表示事件Vi的最迟发生时间 vl(i) = 从顶点Vi到汇点的最短路径长度; 是在保证汇点Vn 在Ve[i] 时刻完成的前提下，事件Vi的允许的最迟开始时间。 9 8 7 6 4 5 3 2 1 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4

23 vi vj ak dut(<i,j>)
关键路径 e(i)——表示活动ak的最早开始时间 设活动ak在边< Vi , Vj >上, 则e(k)是从源点V1到顶点Vi 的最长路径长度。因此, e[k] = Ve[i]。 l(i)——表示活动ak的最迟开始时间 l(k)是在不会引起时间延误的前提下, 该活动允许的最迟开始时间。 l(k) = Vl(j) - dut(<i,j>)。 其中, dut(<i,j>)是完成 ak 所需的时间。 l(i)-e(i)——表示完成活动ai的时间余量,即活动 ak的最早可能开始时间和最迟允许开始时间的时间余量。 关键活动——关键路径上的活动叫~，即l(i)=e(i)的活动 9 8 7 6 4 5 3 2 1 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 vi vj ak dut(<i,j>)

24 关键路径 求关键活动(e(i)=l(i))的方法: 设活动ai用弧<j,k>表示，其持续时间记为：dut(<j,k>) 则有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut(<j,k>) 如何求Ve(j)和Vl(j)？ vi vj ak dut(<i,j>)

25 （1）输入e条弧〈j，k〉，建立AOV-网的存储结构；
(2)求Ve[i]的递推公式 从源点v1(或v0)出发，令ve[1]=0，向前推： ve(j)=Max{ve(i)+dut(<i,j>)} <i,j>属于所有以第j个顶点为头的弧的集合。 ai

26 (3)求Vl[i]的递推公式 从汇点vn出发，令vl[n-1]=ve[n-1]，反向递推: vl(i)=Min{vl(j)-dut(<i,j>)} <i,j>属于所有以第i个顶点为尾的弧的集合。

27 这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。
为了简化算法, 假定在求关键路径之前已经对各顶点实现了拓扑排序, 并按拓扑有序的顺序对各顶点重新进行了编号。 可利用拓扑排序得到的顶点次序进行向汇点的递推，向源点的递推按相反的顺序进行即可，不必再重新排序。

28 （4）根据各顶点的ve和vl值，求每条弧ak的最早开始时间e（k）和最迟开始时间l（k）。若某条弧满足条件e（k）=l（k），则为关键活动。
由关键活动组成的从源点到汇点的路径即为关键路径。

29 求关键路径步骤 求Ve(i) 求Vl(j) 求e(i) 求l(i) 计算l(i)-e(i) 9 8 7 6 4 5 3 2 1 a2=4
活动 e l l-e a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11  顶点 Ve Vl 2 V1 V2 V3 V4 V5 V6 V7 V8 V9 6 4 5 7 16 14 18 6 8 7 10 16 14 18 3 6 4 6 2 5 8 3 7 7 7 10 3 16 14

30 时间余量为零的活动都是关键活动，即为a1，a4，a7，a8，a10，a11。
这些关键活动构成两条关键路径，即关键路径(V1，V2，V5，V7，V9)和(V1，V2，V5，V8，V9)。 在安排工程时，对于关键活动和余量小的活动应重点保证，余量较大的活动可适当地放松些，对非关键活动加速进行，并不能使整个工程提前完成，只有提高关键路径上的活动的效率，才能缩短整个工程的工期。

31 一个工程实例： 施工阶段 1 2 3 挖土 8 6 垫层 5 砌基 10 7 回填 4 挖土 垫层 回填 砌基 20 10 16 25 总工期 = =61 分阶段施工缩短后的工期=42 挖1 挖2 挖3 6 6 8 6 垫1 垫2 垫3 5 5 10 砌1 砌2 8 7 砌3 回2 回3 回1 4 3 3

32 小结 拓扑排序 关键路径 应用领域、求解步骤、算法实现过程 AOV网——用顶点表示活动 应用领域 AOE网：边表示活动的网。 求解步骤
求Ve(i)、求Vl(j)、求e(i)、求l(i)、计算l(i)-e(i)

33 作业： 求关键活动及关键路径 a4=3 1 2 3 4 5 6 a1=3 a2=2 a5=4 a3=2 a6=3 a7=2 a8=1