数据结构第七章-图.ppt

《数据结构第七章-图.ppt》由会员分享，可在线阅读，更多相关《数据结构第七章-图.ppt（99页珍藏版）》请在装配图网上搜索。

1、2020/10/12 1 第 7章 图 图是一种 多对多 的结构关系，每个元素可以有零个或多 个直接前趋；零个或多个直接后继 。 2 【 重点掌握 】 ： 1. 图的两种遍历方法：遍历的定义、深度优先搜索遍历和 广度优先搜索遍历的算法； 2. 应用图的遍历算法判断图的连通性及求图的生成树； 3. 用 Prim、 Kruskal算法求图的最小生成树； 4. 用 Dijkstra算法求解单源最短路径问题；用 Floyd算法求 所有顶点间的最短路径问题； 5. 利用 AOV网进行拓扑排序；利用 AOE网求关键路径问题； 【 掌 握 】 ： 1. 掌握图的定义和术语； 2. 图的各种存储结构及其构造算

2、法 、 在实际问题中的求解 效率 。 3 7.3 图的遍历 7.3 图的遍历： 从图的某顶点出发，访问图中所有顶点， 并且每个顶点仅访问一次。 图结构的遍历复杂性： （ 1）在图结构中，没有一个 “ 自然 ” 的首结点，图中的任 意一个顶点都可以作为第一个被访问的结点 （ 2）在非连通图中，从一个顶点出发，只能访问它所在的 连通分量上的所有顶点，因此，还需考虑 如何选取下一个出 发点 以访问图中的其余连通分量 （ 3）在图结构中，如果有回路存在，那么一个顶点被访问 后，有可能沿回路又回到该顶点，考虑 如何避免重复访问 （ 4）在图结构中，一个顶点可以和其他多个顶点邻接，当 这样的顶点访问过后，

3、考虑 如何选取下一个要访问的顶点的 问题 4 图的遍历方法有深度优先遍历和广度优先遍历两种。 7.3.1 深度优先搜索 方法： （ 1）从图的某一顶点 V0出发，访问此顶点； （ 2）依次从 V0的未被访问的邻接点出发，深度优先遍历图， 直至图中所有和 V0相通的顶点都被访问到。 若此时图中 尚有顶点未被访问，则另选图中一个未被访问的顶点作起点， 重复上述过程，直至图中所有顶点都被访问到。 5 V0 V7 V6 V5 V4 V3 V2 V1 若图的存储结构为邻接表，则 访问邻接点的顺序不唯一， 深度优先序列不是唯一的 V1 V2 V7 V6 V5 V4 V0,V1,V3,V4,V7,V2,V5

4、,V6, 求图 G以 V0为起点的的深度优先序列（设存储结构为邻接 矩阵） 6 void DFS(Graph G, int v) /* 从第 v个顶点出发，递归地深度优先遍历图 G*/ /* v是顶点在一维数组中的位置，假设 G是非空图 */ visitedv =1; Visit(v); /*访问第 v个顶点 */ for ( w=FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w) ) if (!visitedw) DFS(G, w); /*对 v的尚未访问的邻接顶点 w递归调用 DFS*/ 辅助数组： int visitedMax_Vertex_Num ;

5、 访问标志数组 ,全局变量，初始时所有分量 全为 0， visitedv=1表示顶点 v已被访问 . visited 0 1 2 3 4 0 0 0 0 0 深度优先遍历算法 : 7.3 图的遍历 7 7.3 图的遍历 在 邻接表 存储结构上实现深度优先搜索 : void DFSTraverseAL(ALGraph G) /*深度优先遍历以邻接表存储的图 G*/ int i; for (i=0;iG.vexnum; + i) visitedi=0; /*标志数组初始化 */ for(i=0;inextarc) w=p-adjvex; /*w是 v的邻接顶点的序号 */ if (!visited

6、w) DFSAL(G, w); /*若 w尚未访问 , 递归调用 DFS*/ /*DFSAL*/ 7.3 图的遍历 9 在遍历时，对图中每个顶点至多调用一次 DFS函数，因为 一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。 因此，遍历图的过程实质上是对每个顶点查找其邻接点的过 程。其耗费的时间则取决于所采用的存储结构。 用邻接矩阵做图的存储结构时，查找 各个 顶点的邻接点 所需的时间为 O(n2)，其中 n为图中顶点数。当以邻接矩阵做 存储结构时，深度优先搜索遍历图的时间复杂度为 O(n2+n)。 当以邻接表做图的存储结构时，找邻接点所需时间为 O(e)， 其中 e为无向图中边的数或有

7、向图中弧的数。因此， 当以邻接表做存储结构时，深度优先搜索遍历图的时间复杂 度为 O(n+e)。 7.3 图的遍历 10 图中某顶点 v出发： 1）访问顶点 v ； 2）访问 v的所有未被访问的邻接点 w1 ,w2 , w k ； 3）依次从这些邻接点出发，访问它们的所有未被访问的邻 接点 ; 依此类推，直到图中所有访问过的顶点的邻接点 都被访问； 7.3.2 广度优先遍历 7.3 图的遍历 11 V0 V7 V6 V5 V4 V3 V2 V1 V0,V1,V2, V3,V4,V7,V5,V6 V3 V6 V5 若图的存储结构为邻接表，则 访问邻接点的顺序不唯一， 深度优先序列不是唯一的 求图

8、 G以 V0为起点的的广度优先序列（设存储结构为邻 接矩阵） 先被访问的顶点，其 邻接点也要先被访问 设一队列保存已访问 的顶点 12 Q 在邻接表存储结构上的广度优先搜索 V0 V1 V2 V3 V4 V7 V5 V6 V1 V2 V3 V0 V4 V7 V5 V6 V0 V7 V6 V5 V4 V3 V2 V1 7.3 图的遍历 7 0 1 2 V0 V2 V3 V1 data firstarc 0 1 adjvex next 3 V4 3 0 5 1 1 2 7 4 5 6 4 V5 V6 V7 2 6 2 5 1 4 7 6 13 void BFSTraverse(MGraph G)

9、/*从 v出发，广度优先遍历连通图 G*/ /*使用辅助队列 Q和访问标志数组 visited*/ for (v=0; vG.vexnum; +i) visitedv=0; InitQueue(Q, G.vexnum); /*初始化空的辅助队列 Q*/ for (v=0;vG.vexnum;+v) if(!visitedv) /*若 v尚未访问 */ visitedv=1; Visit(v); EnQueue(Q,v); while (!QueueEmpty_Sq(Q) DeQueue(Q,u); /*队头元素出队 ,并赋值给 u*/ /*访问 u所有未被访问的邻接点 */ for(w=0;

10、wG.vexnum; w+;) if (G.arcsu,w.adj Visit(w); EnQueue(Q,w); /*while*/ /*BFSTraverse*/ 7.3 图的遍历 14 第七 章 图 7.4 连通网的最小生成树 7.4.1 生成树 7.4.2 最小生成树 7.4.3 构造最小生成树的 Prim算法 7.4.4 构造最小生成树的 Kruskal算法 15 7.4.1 生成树 生成树： 包含了无向图 G所有顶点的 极小 连通子图。 1） “ 极小 ” 含义：一个有 n个顶点的连通图的生成树有 n-1条边，删除任何一条边，子图不再连通；在生成树中 再加一条边必然形成回路。（生成

11、树包含了图中的所有 顶点，但只有足以构成生成树的 n-1条边） 2）一个图可以有许多棵不同的生成树； 3）生成树中任意两个顶点间的路径是唯一的； 4）含 n个顶点 n-1条边的图不一定是生成树。 7.4 最小的生成树 16 7.4 最小的生成树 生成树的含义： n个 顶点的图 最多可存在 n(n-1)/2条边 线路。求生成树是为了在网络中连通 n个顶点而选择最少的 边 (n 1)。 例如：一个通信网络中，节点代表了路由器，为了使 各路由器之间是连通的（数据可达），且不形成回路 (数据 回到发送方 )，则需建立该网络的生成树。 17 求生成树的方法： 利用遍历算法。 从连通图中的任一顶点出发进行

12、遍历时，除出发 点外，其余顶点必须通过一条边才能到达，所以遍历 过程中经历的边有 n-1条，它和 n个顶点组成了连通图 的一棵生成树。 由深度优先搜索得到的是深度优先生成树；由广度 优先搜索得到的是广度优先生成树。 18 V0 V7 V6 V5 V4 V3 V2 V1 深度遍历： V0V1V3V4V7V2 V5V6 V0 V7 V6 V5 V4 V3 V2 V1 7.4 最小的生成树 V0 V7 V6 V5 V4 V3 V2 V1 深度优先搜索生成树 19 广度遍历： V0 V1 V2 V3 V4 V7 V5 V6 V0 V7 V6 V5 V4 V3 V2 V1 V0 V7 V6 V5 V4

13、V3 V2 V1 广度优先搜索生成树 7.4 最小的生成树 V0 V7 V6 V5 V4 V3 V2 V1 20 7.4.2 最小生成树的概念 由生成树的定义可知，无向连通图的生成树不是惟一的。 问题的提出： 设要在 n个城市间建立通信联络网，顶点 表示城市，权表示城市间建立通信线路所需花费代价。 希望找到一棵生成树，它的每条边上的权值之和（即建立 该通信网所需花费的总代价）最小 最小代价生成树。 7.4 最小的生成树 21 最小生成树定义： 对于一个网络，它的所有生成树 中边权值最小的生成树称为最小生成树。 问题分析： n个城市间建立通信网，如何在可能的线路 中选择 n-1条，能把所有城市（

14、顶点）均连起来，且总 耗费（各边权值之和）最小。 即：如何在保证 n点连通 的前题下最节省经费 ? 22 1. Prim 法基本步骤 设连通网络 G=V,E。集合 U存放 G的最小生成树中的 顶点，集合 T存放最小生成树之外的顶点。 (1)从 G中选择某一顶点 u0出发，在与它关联的边中选择一 个边权最小的边 (u0,v);将顶点 v加入最小生成树的 顶点 集合 U，在 集合 T 中删除该顶点； (2)用顶点 v到集合 T中顶点的边权 “ 更新 ” 原集合 U中顶点 到 集合 T中顶点的最小边权； (3)从一个顶点在 U中，而另一个顶点在 T中的各条边中选择 权值最小的边 (u,v),把顶点

15、v加入到 集合 U 中。 (4)重复 (2) 、 (3)，直到网络中的所有顶点都加入到生成树 顶点集合 U中为止。 7.4.3 构造最小生成树的 Prim算法 7.4 最小的生成树 23 V3 V1 V4 V6 V5 V2 6 5 1 U= V1 V3 V1 V4 V6 V5 V2 5 1 6 5 4 V3 V4 V6 V5 V2 1 V1 U= V1,V3 V3 V1 V4 V6 V5 V2 1 6 5 4 2 V3 V1 V4 V6 V5 V2 5 1 6 5 4 U= V1,V3,V6 7.4 最小的生成树 V3 V1 V4 V6 V5 V2 3 6 5 2 1 6 5 5 4 6 2.

16、 过程演示 24 V3 V1 V4 V6 V5 V2 1 6 5 4 2 U= V1,V3,V6,V4 V3 V1 V4 V6 V5 V2 1 6 5 4 2 U= V1,V3,V6,V4,V2 V3 V1 V4 V6 V5 V2 1 5 4 2 3 U= V1,V3,V6,V4,V2,V5 7.4 最小的生成树 V3 V1 V4 V6 V5 V2 3 6 5 2 1 6 5 5 4 6 Prim 算法的时间复杂度为 O(n2) 25 7.4.3 构造最小生成树的 Kruskal算法 1.基本思想：按网中权值递增的顺序构造最小生成树。 2.基本步骤 1）设连通网 G=(V,E)，令最小生成树初

17、始状态是只有 n个 顶点而无边的非连通图 T=(V,)，每个顶点自成一个连 通分量； 2）在 E中选取代价最小的边，若该边依附的顶点落在 T中 不同的连通分量上，则将此边加入到 T中；否则，舍去 此边，选取下一条代价最小的边； 3）依此类推，直至 T中所有顶点都在同一连通分量上为 止。 7.4 最小的生成树 26 V3 V1 V4 V6 V5 V2 V3 V4 V6 V5 V2 1 V1 V3 V1 V4 V6 V5 V2 1 2 V3 V1 V4 V6 V5 V2 1 2 3 V3 V1 V4 V6 V5 V2 1 6 4 2 3 7.4 最小的生成树 V3 V1 V4 V6 V5 V2 3

18、 6 5 2 1 6 5 5 4 6 3. 过程演示 27 V3 V1 V4 V6 V5 V2 1 6 5 4 2 3 V3 V1 V4 V6 V5 V2 3 6 5 2 1 6 5 5 4 6 7.4 最小的生成树 Kruskal 算法的时间复杂度为 O(ne)。 28 7.5 单源最短路径 (Shortest Path) 从一个源点到其他各点的最短路径 29 交通咨询系统 、 通讯网 、 计算机网络中经常要寻找两结 点间最短路径 。 例如：交通咨询系统中：咨询 A到 B的最短路 径；计算机网中如何发送 E-mail才最节省费用 （ 使 E-mail 由 A到 B沿最短路径传送 ） 。 设用

19、带权的有向图表示一个交通运输网，图中： 顶点 表示城市 边 表示城市间的交通联系 权 表示此线路的长度或沿此线路运输所花的时间 或费用等 这类问题归结为从某顶点出发，沿图的边到达另一顶点 所经过的路径中，各边上权值之和最小的一条路径 最短 路径。路径上的第一个顶点为源点，最后一个顶点为终点。 问题的提出 : 7.5 最短路径 30 最短路径问题： 如果从图中某一顶点 (源点 )到达另一 顶点 (终点 )的路径可能不止一条 ， 如何找到一条路径 使沿此路径上各边上的权值总和达到最小 。 31 从一个源点到其他各点的最短路径 1. 问题的提法：给定一个带权有向图 D与源点 v，求从 v到 D中其它

20、顶点 的最短路径。 7.5 最短路径 10 长度 最短路径 30 50 90 2. 迪杰斯特拉算法（ Dijkstra） （ 1） 基本思想 为求得这些最短路径， Dijkstra提出 按路径长度的递增次序，逐 步产生最短路径 的算法。首先求出长度最短的一条最短路径，再参照它 求出长度次短的一条最短路径，依此类推，直到从顶点 v到其它各顶点 的最短路径全部求出为止。 32 依据算法的基本思想把 V分成两组： （ 1） S：已求出最短路径的顶点的集合 （ 2） V-S=T：尚未确定最短路径的顶点集合 将 T中顶点按如下规则加入到 S中： （ 1）按递增的次序产生最短路径：从源点 V0到 S中各顶

21、点 的最短路径长度都不大于从 V0到 T中任何顶点的最短路径长 度 ; （ 2）待求的最短路径最多以已求出最短路径的顶点为中间 点：从 V0到某顶点的最短路径中，只将 S中的顶点作为中间 点 33 （ 2） Dijkstra 算法的基本步骤 设 V0是源点 ， 初使时令 S=V0,T=其余顶点 ， T中顶点对 应的距离值若存在 ， 边权值为 弧上的权值；若 不存在 ， 边权值为 。 1）从 T中选取一个其距离值最小的顶点 W，加入 S； 2） 对 T中顶点的距离值进行修改：先求出 V0到 Vi中 间只经 S中结点的最短路径；若加进 W作中间顶点后从 V0到 Vi的距离值 比 不加 W的路径要短

22、，则修改此距离值； 上述最短路径中长度最小者即为下一条长度最短 的路径； 将所求最短路径的终点加入 S中； 3） 重复 2） 直到 S中包含所有顶点 ， 即 S=V为止 。 7.5 最短路径 34 1）图用带权邻接矩阵存储； 2） 引入一个辅助数组 dist。它的每一个分量 disti表示 当前找到的从源点 v0 到终点 vi 的最短路径的长度 初始状态： 若从源点 v0 到顶点 vi有边，则 disti为该边上的权 值； 若从源点 v0 到顶点 vi 没有边，则 disti为 。 3）数组 path表示从 V0到各终点的最短路径上，此顶点 的 前一顶点 的序号；若从 V0 到某终点无路径，则

23、用 -1 作为该结点前一顶点的序号 4)数组 s标识 V0 到该结点的最短路径是否求出。 0表示 没求出， 1表示已求出。 7.5 最短路径 (3) 算法实现 35 7.5 最短路径 2 60 0 0 30 1 3 50 1 0 10 1 2 2 60 1 0 30 1 3 50 1 0 10 1 4 3 90 0 0 30 1 3 50 0 0 10 1 3 0 100 0 0 30 0 1 60 0 0 10 1 1 0 100 0 0 30 0 -1 0 0 10 0 0 P4 d4 S4 P3 d3 S3 P2 d2 S2 P1 d1 S1 顶点 4 顶点 3 顶点 2 顶点 1 选

24、取 点 0 1 2 3 4 36 如何从表中读取源点 0到终点的最短路径 ？ 以顶点 4为例： (1) V0到顶点 4的最短路径为 60。 (2) path4=2 path2=3 path3=0 ； 反过来排列，得到路径 0, 3, 2, 4，即 V0到顶点 V4的最短路径。 7.5 最短路径 2 60 0 0 30 1 3 50 1 0 10 1 2 2 60 1 0 30 1 3 50 1 0 10 1 4 3 90 0 0 30 1 3 50 0 0 10 1 3 0 100 0 0 30 0 1 60 0 0 10 1 1 0 100 0 0 30 0 0 0 0 10 0 0 P4

25、d4 S4 P3 d3 S3 P2 d2 S2 P1 d1 S1 顶点 4 顶点 3 顶点 2 顶点 1 选 取 点 37 Dijkstra 算法的时间复杂度为 O(n2) 38 7.6 AOV网与拓扑排序 39 7.6.1 有向无环图的概念 1. 有向无环图（ directed acycline graph） ：没有回路的有向图。 含有公共子式的表达式 例如：表达式 (a+b)*(a+b-e/f) a - + b * / e f 用 有向无环图 表示的表达式 流程图： 工程流程、生产过程中工序流程、程序流程、课程的流 程。常用的两种有向无环图是： AOV网， AOE网。 7.6 有向无环图及

26、其应用 - a + b * / e f a + b 用 二叉树 表示的表达式 40 7.6.2 AOV网与拓扑排序 1. AOV网 (Activity On Vertex network) 用顶点表示 活动 ， 边表示 活动的顺序关系 的有向图称为 AOV网。 在 AOV网中，若从顶点 i到顶点 j有一条有向路径。则顶点 i是顶点 j的前驱， j是 i的后继。若 是网中一条弧，则 i是 j的直接前驱， j是 i的直接后继。 在 AOV网中，每一条弧表示了活动之间存在的制约关系。 注： AOV网中不允许有回路，这意味着某项活动以自己为 先决条件。 例如：计算机专业的学生必须学习一系列的基本课和专

27、 业课。学生应按照怎样的顺序来学习呢？ 可以把这个问 题看做一个大的工程，其活动就是学习每一门课程。 7.6 有向无环图及其应用 41 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 无 无 C1,C2 C3， C9 C2 C4 C5 C4 C1 C4， C9 C4,C7 课程代号 课程名称 先修课 程序设计基础 高等数学 离散数学 数据结构 普通物理 人工智能 计算机原理 算法分析 高级语言 编译系统 操作系统 C1、 C2是独立于其它课程的基础课，而另一些课程必须 在学完作为它的基础课后才能开始，即有先行课。先行条 件规定了课程之间的优先关系。 计算机专业的课程设置及

28、其关系 7.6 有向无环图及其应用 42 顶点表示课程，弧表示前提条件活动。若课程 i是课程 j的先行课， 则必然存在弧 。由此得到如下 AOV网： 在安排学习顺序时，必须保证在学习某门课前，已经学习了其先行课。 如何设置这些课程的学习顺序，才能无矛盾、顺利地完成学业？ 7.6 有向无环图及其应用 C1 程序设计基础 C3 离散数学 C2 高等数学 C4 数据结构 C5 普通物理 C6 人工智能 C7 计算机原理 C8 算法分析 C9 高级语言 C10 编译系统 C11 操作系统 43 2. 拓扑排序 拓扑序列： 有向图 D的一个顶点序列称作一个拓扑序列， 对于该序列中任两顶点 v、 u，若在

29、 D中 v是 u前趋，则在序 列中 v也是 u前趋。 拓扑排序： 把 AOV网络中各顶点按照它们相互之间的领 先关系排列成一个线性序列的过程。 拓扑排序的应用： 判断工程流程的是否合理 . 如何判断 AOV网是否 存在有向回路？ 利用拓扑排序检测 AOV网中 是否存在环： 对有向图构 造其顶点的拓扑有序序列， 若网中所有顶点都在它的 拓扑有序序列中，则该 AOV 网必定不存在环。 7.6 有向无环图及其应用 44 3.拓扑排序算法 （ 1）在 AOV网中选一个 没有前驱的顶点 v并将其输出； （ 2）从网中删除顶点 v和 所有以 v为尾的弧 ； （ 3）重复 (1)、 (2)，直至全部顶点均已

30、输出；或者当图 中不存在无前驱的顶点为止。 7.6 有向无环图及其应用 45 C1 C3 C2 C9 C5 C10 C7 C6 C8 C11 C4 拓扑序列： C1 7.6 有向无环图及其应用 46 C3 C2 C9 C5 C10 C7 C6 C8 C11 C4 拓扑序列： C1， C2 拓扑序列： 7.6 有向无环图及其应用 47 C3 C9 C5 C10 C7 C6 C8 C11 C4 拓扑序列： C1， C2 拓扑序列： ， ， C3 7.6 有向无环图及其应用 48 C9 C5 C10 C7 C6 C8 C11 C4 拓扑序列： C1， C2， C3 拓扑序列： ， ， ， C9 7.

31、6 有向无环图及其应用 49 C5 C10 C7 C6 C8 C11 C4 拓扑序列： C1， C2， C3， C9 拓扑序列： ， ， ， ， C4 C5 C10 C7 C6 C8 C11 拓扑序列： C1， C2， C3， C9， C4， C5 C10 C7 C6 C8 C11 拓扑序列： C1， C2， C3， C9， C4， C5， C7 C10 C6 C8 C11 拓扑序列： C1， C2， C3， C9， C4， C5， C7， C10， C6， C8， C11 一个 AOV网的拓扑 序列不是唯一的。 如何计算机上实现 对有向图的拓扑排序？ 7.6 有向无环图及其应用 50 拓扑排

32、序算法 : （ 1）在 AOV网中选一个 没有前驱的顶点 v并将其输出； （ 2）从网中删除顶点 v和 所有以 v为尾的弧 ； （ 3）重复 (1)、 (2)，直至全部顶点均已输出；或者当图 中不存在 无前驱 的顶点为止。 7.6 有向无环图及其应用 拓扑排序方法的另一种等价描述： （ 1） 选择一 入度为 0顶点 v，输出； （ 2） 将 v邻接到的顶点的入度减 1； （ 3） 重复 (1)、 (2)，直至全部顶点均已输出 ;或图中 没有 入度为 0的顶点为止。 51 拓扑排序的数据结构： 以邻接表存储有向图，并在顶点结点中增加该顶点 的入度信息。 算法： 1）为方便查找入度为 0的元素，将

33、邻接表中所有入度为 0的顶点进栈 2）栈非空时，输出栈顶元素 Vj并退栈； 3）在邻接表中查找 Vj的直接后继 Vk，把 Vk的入度减 1； 若 Vk的入度为 0则进栈； 重复上述操作直至栈空为止。若栈空时输出的顶点 个数不是 n，则有向图有环；否则，拓扑排序完毕。 52 例 : 0 1 2 3 4 5 0 1 2 2 in link 4 4 3 2 vex next 3 1 4 1 3 0 0 1 2 3 4 5 3 2 1 0 4 0 5 top 7.6 有向无环图及其应用 53 0 1 2 2 in link 4 4 3 2 vex next 3 1 4 1 3 0 0 1 2 3 4

34、5 输出序列： 5 3 2 1 0 4 0 5 top 7.6 有向无环图及其应用 54 0 1 2 2 in link 4 4 3 2 vex next 3 1 4 1 3 0 0 1 2 3 4 5 输出序列： 5 p 3 2 1 0 4 0 top 7.6 有向无环图及其应用 55 0 1 2 2 in link 4 4 3 2 vex next 2 1 4 1 3 0 0 1 2 3 4 5 p 3 2 1 0 4 0 top 输出序列： 5 7.6 有向无环图及其应用 56 0 1 2 2 in link 4 4 3 2 vex next 2 1 4 1 3 0 0 1 2 3 4

35、5 p 输出序列： 5 3 2 1 0 4 0 top 7.6 有向无环图及其应用 57 0 1 1 2 in link 4 4 3 2 vex next 2 1 4 1 3 0 0 1 2 3 4 5 p 3 2 1 0 4 0 top 输出序列： 5 7.6 有向无环图及其应用 58 0 1 1 2 in link 4 4 3 2 vex next 2 1 4 1 3 0 0 1 2 3 4 5 p=NULL 3 2 1 0 4 0 top 输出序列： 5 7.6 有向无环图及其应用 59 0 1 1 2 in link 4 4 3 2 vex next 2 1 4 1 3 0 0 1 2

36、 3 4 5 输出序列： 5 0 3 2 1 0 4 top 7.6 有向无环图及其应用 60 0 1 1 2 in link 4 4 3 2 vex next 2 1 4 1 3 0 0 1 2 3 4 5 p 3 2 1 0 4 top 输出序列： 5 0 7.6 有向无环图及其应用 61 0 1 0 2 in link 4 4 3 2 vex next 2 1 4 1 3 0 0 1 2 3 4 5 p 3 3 2 1 0 4 top 输出序列： 5 0 7.6 有向无环图及其应用 62 0 1 0 2 in link 4 4 3 2 vex next 2 1 4 1 3 0 0 1 2

37、 3 4 5 p 3 3 2 1 0 4 top 输出序列： 5 0 7.6 有向无环图及其应用 63 0 0 0 2 in link 4 4 3 2 vex next 2 1 4 1 3 0 0 1 2 3 4 5 p 3 3 2 1 0 4 top 2 输出序列： 5 0 7.6 有向无环图及其应用 64 0 0 0 2 in link 4 4 3 2 vex next 2 1 4 1 3 0 0 1 2 3 4 5 p 3 3 2 1 0 4 top 2 输出序列： 5 0 7.6 有向无环图及其应用 65 0 0 0 1 in link 4 4 3 2 vex next 2 1 4 1

38、 3 0 0 1 2 3 4 5 p 3 3 2 1 0 4 top 2 输出序列： 5 0 7.6 有向无环图及其应用 66 0 0 0 1 in link 4 4 3 2 vex next 2 1 4 1 3 0 0 1 2 3 4 5 p=NULL 3 3 2 1 0 4 top 2 输出序列： 5 0 7.6 有向无环图及其应用 67 0 0 0 1 in link 4 4 3 2 vex next 2 1 4 1 3 0 0 1 2 3 4 4 输出序列： 5 0 2 3 3 2 1 0 4 top 7.6 有向无环图及其应用 68 0 0 0 1 in link 4 4 3 2 v

39、ex next 2 1 4 1 3 0 0 1 2 3 4 5 p 3 3 2 1 0 4 top 输出序列： 5 0 2 7.6 有向无环图及其应用 69 0 0 0 1 in link 4 4 3 2 vex next 1 1 4 1 3 0 0 1 2 3 4 5 p 3 3 2 1 0 4 top 输出序列： 5 0 2 7.6 有向无环图及其应用 70 0 0 0 1 in link 4 4 3 2 vex next 1 1 4 1 3 0 0 1 2 3 4 5 p 3 3 2 1 0 4 top 输出序列： 5 0 2 7.6 有向无环图及其应用 71 0 0 0 0 in li

40、nk 4 4 3 2 vex next 1 1 4 1 3 0 0 1 2 3 4 5 p 3 3 2 1 0 4 top 1 输出序列： 5 0 2 7.6 有向无环图及其应用 72 0 0 0 0 in link 4 4 3 2 vex next 1 1 4 1 3 0 0 1 2 3 4 5 p=NULL 3 3 2 1 0 4 top 1 输出序列： 5 0 2 7.6 有向无环图及其应用 73 0 0 0 0 in link 4 4 3 2 vex next 1 1 4 1 3 0 0 1 2 3 4 5 输出序列： 5 0 2 1 3 3 2 1 0 4 top 7.6 有向无环图

41、及其应用 74 0 0 0 0 in link 4 4 3 2 vex next 1 1 4 1 3 0 0 1 2 3 4 5 p=NULL 3 3 2 1 0 4 top 输出序列： 5 0 2 1 7.6 有向无环图及其应用 75 0 0 0 0 in link 4 4 3 2 vex next 1 1 4 1 3 0 0 1 2 3 4 5 3 2 1 0 4 top 输出序列： 5 0 2 1 3 7.6 有向无环图及其应用 76 0 0 0 0 in link 4 4 3 2 vex next 1 1 4 1 3 0 0 1 2 3 4 5 p 3 2 1 0 4 top 输出序列

42、： 5 0 2 1 3 7.6 有向无环图及其应用 77 0 0 0 0 in link 4 4 3 2 vex next 0 1 4 1 3 0 0 1 2 3 4 5 p 4 3 2 1 0 4 top 输出序列： 5 0 2 1 3 7.6 有向无环图及其应用 78 0 0 0 0 in link 4 4 3 2 vex next 0 1 4 1 3 0 0 1 2 3 4 5 p=NULL 4 3 2 1 0 4 top 输出序列： 5 0 2 1 3 7.6 有向无环图及其应用 79 0 0 0 0 in link 4 4 3 2 vex next 0 1 4 1 3 0 0 1 2

43、 3 4 5 输出序列： 5 0 2 1 3 4 4 3 2 1 0 4 top 7.6 有向无环图及其应用 80 0 0 0 0 in link 4 4 3 2 vex next 0 1 4 1 3 0 0 1 2 3 4 5 p=NULL 3 2 1 0 4 top 输出序列： 5 0 2 1 3 4 7.6 有向无环图及其应用 81 拓扑排序算法分析 : 建邻接表： T(n)=O(n+e) 搜索入度为 0的顶点的时间： T(n)=O(n) 拓扑排序： T(n)=O(n+e) 7.6 有向无环图及其应用 82 7.7 AOE网和关键路径 AOE网 (Activity On Edges) 如

44、果在 无有向环的带权有向图 中 , 用 有向边 表示一个工程中的 各项活动 (Activity), 用 边上的权值 表示 活动的持续时间 (Duration), 用 顶点 表示 事件 (Event)， 每个事件表示在它之前的 活动已完成，在它之后的活动可以开始 . 这样的有向图叫做用边表示活动的网络，简称 AOE网。 AOE网在某些工程估算方面非常有用。 用途 1：计算完成整个工程至少需要多少时间 (假设网络中 没有环 )? 用途 2：为缩短完成工程所需的时间 , 应当加快哪些活动 ? 7.6 有向无环图及其应用 83 顶点表示事件 边表示活动 事件 Vj发生 表示 ak已结束 ak V j

45、Vi 事件 Vi发生 表示活动 ak可以开始 V3 V1 V4 V6 V5 V2 a4=3 a1=3 a2=2 a 6=3 a5=4 a3=2 a7=2 a8=1 AOE网 事件 V1 表示整个工程开始 事件 V6 表示整个工程结束 7.6 有向无环图及其应用 84 说明： AOV网和 AOE网，用都能表示工程各子工程的流程， 一个用顶点表示活动，一个用边表示活动，但 AOV网侧重表 示活动的前后次序， AOE网除表示活动先后次序，还表示了 活动的持续时间等，因此可利用 AOE网解决工程所需最短时 间及哪些子工程拖延会影响整个工程按时完成等问题。实 际应用中采用那一种图，取决于要求解的问题。

46、AOE网具有两个性质 : (1) 只有在某顶点所代表的事件发生之后，从该顶点 出发的弧所代表的活动才能开始 ; (2) 只有在进入一个顶点的各弧所代表的活动都已经 结束，该顶点所代表的事件才能发生。 7.6 有向无环图及其应用 85 2. 关键路径 (Critical Path) 在 AOE网中 , 有些活动 顺序进行 ，有些活动 并行进行 。 整个工程结束的条件：从源点到终点的有向路径可能不 止一条，其长度也不尽相同，但只有各条路径上所有活动 都完成了，整个工程才算完成。 关键路径：完成整个工程所需的时间取决于 从源点到终 点的 最长 路径长度 （该路径上所有活动的持续时间之和）。 这条路径

47、长度最长的路径 就叫做 关键路径 。 7.6 有向无环图及其应用 V3 V1 V4 V6 V5 V2 a4=3 a1=3 a2=2 a 6=3 a5=4 a3=2 a7=2 a8=1 AOE网 86 关键路径长度 是整个工程所需的最短工期 ,即要缩短整 个工期，必须加快关键活动的进度。 87 3. 关键路径的确定 设活动 ai用弧 表示，其持续时间记为： dut()。 (1)事件 Vk 的最早可能开始时间 Vek 是从源点 V0 到顶点 Vk的最长路径长度。决 定了所有从顶点发出的弧所代表的活动能够开 工的最早时间 . 根据 AOE网的性质，只有进入 VK的所有活 动 （ 1jn-1)都结束时

48、 , Vk代表的事 件才能发生。计算 Vk的的最早可能开始时间方 法如下 : 从 Ve1=0开始递推， Vek = Maxvej + dut() Vj Vk Vj 1 jn-1 7.6 有向无环图及其应用 88 (2)事件 Vk的最迟允许开始时间 Vlk 是在保证终点 Vn-1 在 Ven-1 时刻完成的前提下 (即不拖延工 期 )，事件 Vk的允许的最迟开始时间。 从 Vln=Ven开始递推 ， Vlk = Minvlj dut() Vj Vk Vj 2jn 设弧 代表从 Vk出发的活动，为了不 拖延工期， Vk发生的最迟时间必须 保证不推迟 从事件 Vk出发的所有活动 的终点 Vj (2j

49、n)的最迟时间 7.6 有向无环图及其应用 89 (3)活动 ai的最早可能开始时间 ei 设活动 ai 由弧 表示，根据 AOE网 的性质，只有事件 Vk发生了，活动 ai才能开始。 也就是说，活动 ai的最早开始时间等于是 vk的 最早发生时间。因此 , ek = Vei。 (4) 活动 ai的最迟开始时间 li li是在不会引起时间延误的前提下，该活动允许的最迟开始时间。 设活动 ai 由弧 表示，根据 AOE网的性质， ai的最迟开始时 间要保证时间 vj的最迟发生时间不拖后。 li=Vlj - dut() Vj Vk ai (5) 关键活动 活动 ai的 时间余量 为 li - ei

50、（ 最迟可能开始时间和最早允许开始 时间的差）。 定义 li = ei的 活动是没有时间余量的 关键活动 。 7.6 有向无环图及其应用 90 求关键路径步骤 求 Ve(i) 求 Vl(j) 求 e(i) 求 l(i) 计算 l(i)-e(i) V1 V2 V3 V4 V5 V6 V7 V8 V9 顶点 Ve Vl 0 6 4 5 7 7 16 14 18 0 6 6 8 7 10 16 14 18 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 活动 e l l-e 0 0 0 0 2 2 6 6 0 4 6 2 5 8 3 7 7 0 7 7 0 7 10 3 16

51、16 0 14 14 0 0 3 3 9 8 7 6 4 5 3 2 1 a6=2 7.6 有向无环图及其应用 91 注意：网络中各项活动是互相牵涉的，影响关键活动 的因素是多方面的，任何一项活动持续时间的改变都可 能影响关键路径的改变。 关键活动的速度是有限的，只有在不改变网络关键路 径的情况下，提高关键活动的速度才有效。 92 算法实现 以邻接表作存储结构 从源点 V1出发，令 Ve1=0，按拓扑序列求各顶点的 Vei 从汇点 Vn出发，令 Vln=Ven，按逆拓扑序列求其 余各顶点的 Vli 根据各顶点的 Ve和 Vl值，计算每条弧的 ei和 li, 找出 ei=li的关键活动 7.6

52、有向无环图及其应用 93 算法描述 输入顶点和弧信息，建立其邻接表 计算每个顶点的入度 对其进行拓扑排序 在拓扑排序过程中求顶点的 Vei 将得到的拓扑序列进栈 按逆拓扑序列求顶点的 Vli 计算每条弧的 ei和 li,找出 ei=li的关键 活动 94 算法性能 : 在拓扑排序求 Vei和逆拓扑有序求 Vli时 , 所需时间为 O(n+e), 求各个活动的 ek和 lk时所需时间为 O(e), 总共 花费时间仍然是 O(n+e)。 7.6 有向无环图及其应用 95 本章小结 1. 图是一种 多对多 的数据结构，每个元素可以有零个或多 个直接前趋；零个或多个直接后继 。 2. 在图中存在两种关

53、系： 顶点之间的 邻接 关系和边与顶点 间的 关联 关系。 3. 图的存储结构有邻接矩阵、邻接表、十字链表、邻接多 重表等。无论哪一种存储结构都要存储图中的顶点和顶 点间的关系。 4. 图的遍历方法有深度优先遍历和广度优先遍历两种，应 用图的遍历可以判断图的连通性。 96 5. 求生成树是为了在网络中连通 n个顶点而选择最少的边 （ n 1），应用图的遍历可以求图的生成树。 6. 求最小生成树是为了获得在网络中连通 n个顶点的最低 造价的方案， Prim算法的原理是每次向最小生成树中加 顶点和边、 Kruskal算法的原理是每次向最小生成树中 加边。 7. 单源最短路径问题是在网络中求从某顶点出发到达其他 各点的最短路径， Dijkstra算法可以有效解决该问题。 每对顶点间的最短路径问题可以由 Floyd算法解决。 8. 有向无环图包括 AOV网和 AOE网。利用 AOV网可以进行拓 扑排序，为项目中子任务分配可行进度安排。利用 AOE 网可求关键路径，估算完成项目的时间。 97 98 考试题型 选择 待定 判断 填空 待定 简答题 编程题 1 10 99 题型示例 简答题： 队列的状态变化 由遍历序列恢复二叉树 构造哈夫曼树 画图的存储结构 求连通网的最小生成树 求单源最短路径 求拓扑排序 求关键路径 编程题：关于单链表的运算