数据结构 第六章教学课件 .ppt

《数据结构 第六章教学课件 .ppt》由会员分享，可在线阅读，更多相关《数据结构 第六章教学课件 .ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构 第六章教学课件 第六章第六章 图图数据结构数据结构目目录录4 41 12 23 3 图的定义及其常用术语图的定义及其常用术语图的存储结构图的存储结构图的遍历图的遍历生成树和最小生成树生成树和最小生成树5 5图的应用图的应用第六章第六章第六章第六章图图图图总总体要求体要求了解图的定义和术语了解图的定义和术语掌握图的两种存储结构极其构造算法；掌握图的两种存储结构极其构造算法；重点掌握图的两种遍历算法；重点掌握图的两种遍历算法；了解图的连通性问题极其判断；了解图的连通性问题极其判断；了解有向无环图极其应用（拓扑排序和关键路径）了解有向无环图极其应用（拓扑排序和关键路径）了解最短路径问题的解

2、决方法。了解最短路径问题的解决方法。6.1图图的定的定义义及其常用及其常用术语术语u6.1.1 图的定义图的定义在图中的数据元素通常称为顶点，图（在图中的数据元素通常称为顶点，图（在图中的数据元素通常称为顶点，图（在图中的数据元素通常称为顶点，图（GraphGraph）是由）是由）是由）是由顶点集合顶点集合顶点集合顶点集合（VertexVertex）及顶点之间的）及顶点之间的）及顶点之间的）及顶点之间的关系集合关系集合关系集合关系集合（EdgeEdge）组成的一种数据结构。记为组成的一种数据结构。记为组成的一种数据结构。记为组成的一种数据结构。记为G=G=（V V，E E）。）。）。）。无向图

3、无向图有向图有向图G1=(V1,E1)其中其中V1=A,B,C,D,EE1=(A,D),(B,C),(B,D),(B,E),(D,E)G2=(V2,E2)其中其中V2=A,B,C,DE2=,u6.1.2 图的常用术语及含义图的常用术语及含义1有向图和无向图有向图和无向图在图中，根据顶点之间的关系是否有在图中，根据顶点之间的关系是否有方向性方向性可将可将图分为有向图和无向图。对于图分为有向图和无向图。对于无向图无向图，顶点的关，顶点的关系为无向边，用圆括号表示系为无向边，用圆括号表示，如如（x，y）。对于对于有向图有向图来说，顶点间的关系称为有向边，用来说，顶点间的关系称为有向边，用尖括号表示尖

4、括号表示，如，如xy。没有方向性，（没有方向性，（x，y）和（）和（y，x）是等价的，是同一条边。）是等价的，是同一条边。表示从顶点表示从顶点x 发向顶点发向顶点y 的边，的边，x 为始点，为始点，y 为终点。为终点。2完全图、稠密图、稀疏图、网完全图、稠密图、稀疏图、网无向图中边的取值范围：无向图中边的取值范围：0en(n-1)/2。（用（用 n 表示图中顶点数目，用表示图中顶点数目，用 e 表示边的数目。且表示边的数目。且不考虑顶点到其自身的边。）不考虑顶点到其自身的边。）完全图：完全图：完全图：完全图：有有 n(n-1)/2 条边的无向图（即：条边的无向图（即：每两个每两个顶点之间都存在

5、着一条边顶点之间都存在着一条边)称为称为完全图完全图完全图完全图。v2 v1 v3 v4 v5 有向图中弧的取值范围：有向图中弧的取值范围：0en(n-1)。（用（用 n 表示图中顶点数目，用表示图中顶点数目，用 e 表示弧的数目。表示弧的数目。且不考虑顶点到其自身的弧。）且不考虑顶点到其自身的弧。）有向完全图：有向完全图：有向完全图：有向完全图：有有 n(n-1)条弧的有向图条弧的有向图（即：每两个顶点之间都存在着方向相反的两条（即：每两个顶点之间都存在着方向相反的两条弧）称为弧）称为有向完全图有向完全图有向完全图有向完全图。v2 v1 v3 v4 稀疏图：稀疏图：稀疏图：稀疏图：含有很少条

6、边或弧的图。含有很少条边或弧的图。稠密图：稠密图：稠密图：稠密图：含有很多条边或弧的接近完全图的图。含有很多条边或弧的接近完全图的图。权：权：权：权：与图的与图的边边边边或或弧弧弧弧相关的数，权值可以是距离，时间，相关的数，权值可以是距离，时间，价格等。价格等。网：网：网：网：带权的图。带权的图。成都成都12000（流动人口）（流动人口）15000（流动人口（流动人口 成都成都2039（距离）（距离）北京北京 北京北京 3子图子图若有两个图若有两个图若有两个图若有两个图 GG1 1和和和和GG2 2，其中，其中，其中，其中GG1 1=(V=(V1 1，E E1 1)，GG2 2=(V=(V2

7、2，E E2 2)，且满足如下条件：，且满足如下条件：，且满足如下条件：，且满足如下条件：V V2 2 V V1 1,E,E2 2 E1 1即即即即V V2 2 为为为为V V1 1 的子集，的子集，的子集，的子集，E E2 2 为为为为E E1 1 的子集，则称图的子集，则称图的子集，则称图的子集，则称图 GG2 2为图为图为图为图GG1 1 的子图。的子图。的子图。的子图。（a）图）图G （b）图）图G的两个子图的两个子图4邻接点和度邻接点和度对于对于对于对于无向图无向图无向图无向图，假若顶点，假若顶点，假若顶点，假若顶点v v 和顶点和顶点和顶点和顶点w w 之间存在一条边，之间存在一条

8、边，之间存在一条边，之间存在一条边，则称顶点则称顶点则称顶点则称顶点v v 和和和和w w 互为邻接点互为邻接点互为邻接点互为邻接点。和顶点。和顶点。和顶点。和顶点v v 关联的边的数关联的边的数关联的边的数关联的边的数目定义为目定义为目定义为目定义为v v的度。记为的度。记为的度。记为的度。记为ID(V)ID(V)。ID（A）=2ID（B）=3ID（D）=?ID（E）=?对于对于对于对于有向图有向图有向图有向图，由于弧有方向性，则有，由于弧有方向性，则有，由于弧有方向性，则有，由于弧有方向性，则有入度入度入度入度和和和和出度出度出度出度之之之之分。顶点的出度是以顶点分。顶点的出度是以顶点分。

9、顶点的出度是以顶点分。顶点的出度是以顶点v v 为弧尾的弧的数目，记为为弧尾的弧的数目，记为为弧尾的弧的数目，记为为弧尾的弧的数目，记为OD(V)OD(V)。顶点的入度是以顶点。顶点的入度是以顶点。顶点的入度是以顶点。顶点的入度是以顶点v v为弧头的弧的数目，为弧头的弧的数目，为弧头的弧的数目，为弧头的弧的数目，记为记为记为记为ID(V)ID(V)。OD(B)=1，ID(B)=2TD(B)=OD(B)+ID(B)=3试试求求顶顶点点A的入的入度、出度和度。度、出度和度。5路径、简单路径、简单回路路径、简单路径、简单回路路径长度路径长度路径长度路径长度：图中两个顶点之间的路径为两个顶点之：图中两

10、个顶点之间的路径为两个顶点之：图中两个顶点之间的路径为两个顶点之：图中两个顶点之间的路径为两个顶点之间的顶点序列，路径上所含边的数目。间的顶点序列，路径上所含边的数目。间的顶点序列，路径上所含边的数目。间的顶点序列，路径上所含边的数目。简单路径简单路径简单路径简单路径：若序列中第一个顶点和最后一个顶点相：若序列中第一个顶点和最后一个顶点相：若序列中第一个顶点和最后一个顶点相：若序列中第一个顶点和最后一个顶点相同的路径称为回路或环，序列中顶点不重复出现的同的路径称为回路或环，序列中顶点不重复出现的同的路径称为回路或环，序列中顶点不重复出现的同的路径称为回路或环，序列中顶点不重复出现的路径。路径。

11、路径。路径。简单回路简单回路简单回路简单回路：若序列中除第一个顶点和最后一个顶点：若序列中除第一个顶点和最后一个顶点：若序列中除第一个顶点和最后一个顶点：若序列中除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路。相同外，其余顶点不重复的回路。相同外，其余顶点不重复的回路。相同外，其余顶点不重复的回路。6连通图、连通分量、强连通图和强连通分量连通图、连通分量、强连通图和强连通分量连通：连通：连通：连通：从顶点从顶点 v 到到 v 有路径，则说有路径，则说 v 和和 v 是连通的是连通的。连通图：连通图：连通图：连通图：图中任意两个顶点都是连通的。图中任意两个顶点都是连通的。非连通图：非连通

12、图：非连通图：非连通图：图中并非任意两个顶点都是连通的。图中并非任意两个顶点都是连通的。连通分量：连通分量：连通分量：连通分量：无向图的极大连通子图。无向图的极大连通子图。(a)连通图连通图G1(b)非非 连通图连通图G2(c)G2两个连通分量两个连通分量强连通图：强连通图：强连通图：强连通图：有向图的任意两个顶点之间都存在一条有向图的任意两个顶点之间都存在一条有向路径。有向路径。强连通分量：强连通分量：强连通分量：强连通分量：有向图中极大的强连通子图有向图中极大的强连通子图 (a)强连通图强连通图G1(b)非非 强连通图强连通图G2(c)G2三个强连通分量三个强连通分量6.2 图的存储结构图

13、的存储结构u6.2.1邻接矩阵（邻接矩阵（Adjacency Matrix）用两个数组来表示图，一个用两个数组来表示图，一个用两个数组来表示图，一个用两个数组来表示图，一个一维数组一维数组一维数组一维数组，存储图中顶，存储图中顶，存储图中顶，存储图中顶点的信息，一个数点的信息，一个数点的信息，一个数点的信息，一个数二维数组二维数组二维数组二维数组，即矩阵，存储顶点之，即矩阵，存储顶点之，即矩阵，存储顶点之，即矩阵，存储顶点之间相邻的信息，也就是边（或弧）的信息。间相邻的信息，也就是边（或弧）的信息。间相邻的信息，也就是边（或弧）的信息。间相邻的信息，也就是边（或弧）的信息。设图设图设图设图G=

14、G=（V V，E E），有），有），有），有n n 个顶点，则其所对应的邻接个顶点，则其所对应的邻接个顶点，则其所对应的邻接个顶点，则其所对应的邻接矩阵矩阵矩阵矩阵A A 是按如下定义的一个是按如下定义的一个是按如下定义的一个是按如下定义的一个 二维数组：二维数组：二维数组：二维数组：A B C D E FA B C D E F无向图的邻接矩阵的特点？无向图的邻接矩阵的特点？无向图的邻接矩阵的特点？无向图的邻接矩阵的特点？主对角线为主对角线为主对角线为主对角线为 0 0 且一定是对称矩阵。且一定是对称矩阵。且一定是对称矩阵。且一定是对称矩阵。A B C D E FA B C D E F如何求顶

15、点如何求顶点i的度？的度？邻接矩阵的第邻接矩阵的第i行（或第行（或第i列）非零元素的个数。列）非零元素的个数。如何求顶点如何求顶点 i 的所有邻接点？的所有邻接点？将数组中第将数组中第 i 行元素扫描一遍，若行元素扫描一遍，若aij为为1，则顶，则顶点点 j 为顶点为顶点 i 的邻接点。的邻接点。有向图的邻接矩阵一定不对称吗？有向图的邻接矩阵一定不对称吗？不一定，例如有向完全图。不一定，例如有向完全图。如何求顶点如何求顶点 i 的出度、入度？的出度、入度？邻接矩阵的第邻接矩阵的第 i 行元素之和，第行元素之和，第i列元素之和。列元素之和。若若若若GG是网，则邻接矩阵可定义为：是网，则邻接矩阵可

16、定义为：是网，则邻接矩阵可定义为：是网，则邻接矩阵可定义为：无向网无向网A1有向网有向网A2用邻接矩阵方法存储图，很容易确定图中任意两用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连（邻接），但要确定图个顶点之间是否有边相连（邻接），但要确定图中有多少条边，则必须按行、按列对每个元素进中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大，同时，邻接矩行检测，所花费的时间代价很大，同时，邻接矩阵存储空间为阵存储空间为 O(n2)，所以适用于稠密图。，所以适用于稠密图。public class Graphprotected final int MAXSIZE=10

17、;protected final int MAX=999;protected T V;/顶点信息顶点信息protected int arcs;/邻接矩阵邻接矩阵protected int e;/边数边数protected int n;/顶点数顶点数public Graph()public void CreateAdj()public int LocateVex(T v)public void DisplayAdjMatrix()图的邻接矩阵数据类型描述：图的邻接矩阵数据类型描述：【算法算法6-1】在图在图G中查找顶点中查找顶点public int LocateVex(T v)int i;for

18、(i=0;in;i+)if(Vi=v)return i;return-1;【算法算法】分配顶点数组和邻接矩阵分配顶点数组和邻接矩阵public Graph()V=(T)new ObjectMAXSIZE;arcs=new intMAXSIZEMAXSIZE;【算法算法6-2】在屏幕上显示图在屏幕上显示图G的邻接矩阵表示的邻接矩阵表示public void DisplayAdjMatrix()int i,j;System.out.println(图的邻接矩阵表示：图的邻接矩阵表示：);for(i=0;in;i+)for(j=0;jn;j+)System.out.print(+arcsij);Sy

19、stem.out.println();u6.2.2邻接表邻接表(Adjacency List)无向图的邻接表具有如下性质：无向图的邻接表具有如下性质：(1)第第i 个链表中结点的数目为第个链表中结点的数目为第i个顶点的度。个顶点的度。(2)所有链表中结点的数目的一半为图中边的数目。所有链表中结点的数目的一半为图中边的数目。(3)占用的存储单元数目为占用的存储单元数目为n2e。（。（n为顶点数，为顶点数，e为为边数）边数）顶点顶点 vi 的的出度出度出度出度为第为第 i 个个 单链表中的结点个数。单链表中的结点个数。特点：特点：顶点顶点 vi 的的入度入度入度入度为整个为整个单单 链表中邻接点域

20、值是链表中邻接点域值是 i 的结点个数的结点个数。顶点顶点 vi 的的入度入度入度入度为第为第 i 个个 单链表中的结点个数。单链表中的结点个数。顶点顶点 vi 的的出度出度出度出度为整个为整个单单 链表中邻接点域值是链表中邻接点域值是 i 的结点个数的结点个数。（a）有向图）有向图 （b）邻接表）邻接表 （c）逆邻接表）逆邻接表邻接表邻接表逆邻接表逆邻接表V0V1V2V321 3 1v0v1v2v301230 3 0 2 v0v1v2v3012330 练习练习6.3图的遍历图的遍历从图的任意指定顶点出发，依照某种规则去访问图从图的任意指定顶点出发，依照某种规则去访问图中所有顶点，且每个顶点仅

21、被访问一次，这一过程中所有顶点，且每个顶点仅被访问一次，这一过程叫做叫做图的遍历图的遍历图的遍历图的遍历。深度深度深度深度 优先遍历法优先遍历法优先遍历法优先遍历法（Depth_First SearchDFS）和和 广度优先遍历法广度优先遍历法广度优先遍历法广度优先遍历法（Breadth_Frist SearchBFS）V1V2V4V5V3V7V6V8u6.3.1深度优先搜索深度优先搜索方法：方法：1、首先访问出发点、首先访问出发点V；2、然后依次从、然后依次从V 出发搜索出发搜索V的每个邻接点的每个邻接点W，若，若W未曾访问过，则以未曾访问过，则以W为新的出发点继续进行深度优为新的出发点继续

22、进行深度优先搜索遍历，直至图中所有和源点先搜索遍历，直至图中所有和源点V有路径相通的有路径相通的顶点（也称为从源点可达的顶点）均已被访问为止；顶点（也称为从源点可达的顶点）均已被访问为止；3、若此时图中仍有未访问的顶点，则另选一个尚、若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。中所有顶点均已被访问为止。访问标志数组访问标志数组（b）深度优先搜索过程）深度优先搜索过程从顶点从顶点V1出发深度优先遍历的序列为：出发深度优先遍历的序列为：V1、V2、V4、V8、V5、V3、V6、V7还可以是

23、：还可以是：V1、V2、V5、V8、V4、V3、V7、V6V1、V3、V7、V6、V2、V5、V8、V4 1 3 7 4 0 V0 V1 V3 V7 V4 V2 实现：实现：V0V1V3V4V2V6V5V70 1 2 3 4 5 6 7 V0 V1 V2 V3 V4 V5 V6 V7 2 1 0 1 0 1 2 2 3 3 5 4 6 7 7 6 5 4 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 2 V5 5 V6 6 1 1 1 1 1 1 1 1 u6.3.2广度优先搜索广度优先搜索方法：方法：(1)首先访问出发点首先访问出发点V。(2)接着依次访问顶点接着依次访问顶

24、点V的所有邻接点的所有邻接点V1，V2，Vt；(3)然后再依次访问顶点然后再依次访问顶点V1，V2，Vt的所有的所有邻接点。邻接点。(4)如此类推，直至图中所有的顶点都被访问到。如此类推，直至图中所有的顶点都被访问到。从顶点从顶点V出发广度优先遍历的序列为：出发广度优先遍历的序列为：V，W1，W 2，W 8，W7，W 3，W 5，W6，W 4V，W2，W 8，W 1，W3，W 5，W 7，W4，W 6V，W1，W 8，W 2，W7，W 3，W 5，W6，W 4V0 V1 V2 V3 V4 V5 实现：实现：V0V1V3V4V2V6V5V70 1 2 3 4 5 6 7 V0 V1 V2 V3

25、V4 V5 V6 V7 2 1 0 1 0 1 2 2 3 3 5 4 6 7 7 6 5 4 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 V6 V7 1 1 1 1 1 1 1 1 6.4生成生成树树和最小生成和最小生成树树u6.4.1生成树生成树在一个有在一个有n 个顶点的连通图个顶点的连通图G 中，存在一个极小的中，存在一个极小的连通子图连通子图G，G包含图包含图G 的的所有顶点所有顶点，但只有，但只有n-1 条边条边，并且，并且G是是连通连通的，则称的，则称G为图为图G 的的生成树生成树。(a)(a)连通图连通图 (b)(b)深度优先生成树深度优先生成树 (c)(c

26、)广度优先生成树广度优先生成树u6.4.2最小生成树最小生成树某个图所有生成树中必有一棵边的权值总和最小的某个图所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为生成树，我们称这棵生成树为最小生成树，简称为最小生成树最小生成树，记为，记为MST。把生成树把生成树T中各边的权值总和称为该树的权，记为：中各边的权值总和称为该树的权，记为：应用应用：要在：要在 n 个城市间建立通信联络网。顶点个城市间建立通信联络网。顶点：表示表示城市，权：城市间通信线路的花费代价。希望此通信城市，权：城市间通信线路的花费代价。希望此通信网花费代价最小。网花费代价最小。构造最小生成树方

27、法：构造最小生成树方法：方法一：普里姆方法一：普里姆(Prim)算法。算法。V1V6V5V4V3V26513566425算法思想：算法思想：算法思想：算法思想：设设 N=(V,E)是连通网，是连通网，TE 是是 N 上最小生成树中上最小生成树中边的集合边的集合。初始令初始令 U=u0,(u0 V),TE=。在所有在所有 u U,v V-U 的边的边(u,v)E 中，中，找一条代价最小的边找一条代价最小的边(u0,v0)。将将(u0,v0)并入集合并入集合 TE，同时同时 v0 并入并入 U。重复上述操作直至重复上述操作直至 U=V 为止，则为止，则 T=(V,TE)为为 N 的最的最 小生成树

28、。小生成树。V1V3V6V4V2V5图图6.18 普里姆算法构造普里姆算法构造最小生成树过程最小生成树过程方法二：克鲁斯卡尔方法二：克鲁斯卡尔(Kruskal)算法。算法。V1V6V5V4V3V26513566425算法思想：算法思想：算法思想：算法思想：设连通网设连通网 N=(V,E)，令最小生成树令最小生成树初初始状态为始状态为只有只有 n 个个顶点顶点而而无边无边的非连通图的非连通图 T=(V,)，每个顶点自成一个连通分量。，每个顶点自成一个连通分量。在在 E 中选取代价最小的边，若该边依附中选取代价最小的边，若该边依附 的顶点落在的顶点落在 T 中不同的连通分量上（即：中不同的连通分量

29、上（即：不能形成环不能形成环），则将此边加入到），则将此边加入到 T 中；否中；否 则，舍去此边，选取下一条代价最小的边则，舍去此边，选取下一条代价最小的边。依此类推，直至依此类推，直至 T 中所有顶点都在同一中所有顶点都在同一 连通分量上为止。连通分量上为止。V1V6V5V4V3V212345N T 图图6.20 克鲁斯卡尔算法克鲁斯卡尔算法构造最小生成树过程构造最小生成树过程6.5图图的的应应用用u6.5.1最短路径最短路径问题抽象：问题抽象：在在有向网有向网有向网有向网中中 A 点（点（源点源点源点源点）到达）到达 B 点点（终点终点终点终点）的多条路径中，寻找一条各边权值之和最）的多条

30、路径中，寻找一条各边权值之和最小的路径，即小的路径，即最短路径最短路径最短路径最短路径。省道省道(50)济南济南莱芜莱芜泰安泰安国道国道(100)泰莱高速泰莱高速 省道省道 京福高速京福高速京福高速京福高速(120)(120)仲宫仲宫省道省道(60)13 长度长度最短路径最短路径(v0,v1)(v0,v2)(v0,v2,v3)(v0,v2,v3,v4)(v0,v2,v3,v4,v5)(v0,v1,v6)8 13 19 21 20 从从 v1 到到 v7 的路径：的路径：v1、v2、v5、v7：2020v1、v4、v2、v5、v7：14 v1、v2、v7：2323v1、v4、v2、v7：1717

31、v1、v4、v6、v7：2 24 4例：例：v1v2v5v3v6v4v7915126423851116v5v1v6v4v3v2v0856230 13717329源点源点 终点终点 怎样求单源点的最短路径呢怎样求单源点的最短路径呢?2、迪杰斯特拉（、迪杰斯特拉（Dijkstra）算法：）算法：按路径长度递增次序产生各顶点的最短路径。按路径长度递增次序产生各顶点的最短路径。1、将将 源源 点点 到到 终终 点点 的的 所所 有有 路路 径径 都都 列列 出出 来来，然后在其中选最短的一条。然后在其中选最短的一条。缺点：缺点：当路径特别多时，特别麻烦；当路径特别多时，特别麻烦；没有规律可循。没有规律

32、可循。Dijkstra 算法：按路径长度递增次序产生最短路径算法：按路径长度递增次序产生最短路径Dijkstra 算法步骤：算法步骤：终终点点从从 v0 到各终点的最短路径及长度到各终点的最短路径及长度i=1i=2i=3i=4i=5i=6v1v2v3v4v5v6vj S1383032v2813133032v11313302220v38+5 192220v48+5+6 2120v613+7 21v5 8+5+6+2 v5v1v6v4v3v2v0856230 13717329v2v3v1v4v5v6v042301101006060501030终点终点 i=1 i=2 i=3 i=4v1v2v3v4

33、vj从从 v0 到各终点的最短路径及长度到各终点的最短路径及长度dist数组记录路径长度数组记录路径长度path数组路径中最后一数组路径中最后一个顶点个顶点10001000902703300-1100300604604v4v2v3v1练习：求从练习：求从V0出发，到其它各顶点的最短路径。出发，到其它各顶点的最短路径。u6.5.2拓扑排序拓扑排序有向图中，若以图中的顶点表示活动，以弧表示有向图中，若以图中的顶点表示活动，以弧表示活动之间的优先关系，这样的有向图称为活动之间的优先关系，这样的有向图称为AOV网网（Active On Vertex Network）。）。1、若若是是AOV网中的弧，则

34、称网中的弧，则称vi是是vj的直接前的直接前驱，驱，vj是是vi的直接后继。的直接后继。2、在、在AOV网中，不应该出现有向环路。网中，不应该出现有向环路。每个活动之间有时存在一定的先决条件关系，每个活动之间有时存在一定的先决条件关系，即在时间上有着一定的相互制约的关系。即在时间上有着一定的相互制约的关系。图图6.24表示课程之间关系的表示课程之间关系的AOV网网判断图中是判断图中是否存在回路否存在回路的方法是：的方法是：拓扑排序拓扑排序对对AOV网进行拓扑排序的方法的步骤如下：网进行拓扑排序的方法的步骤如下：(1)从有向图中选一个没有前驱的顶点，并输出之从有向图中选一个没有前驱的顶点，并输出

35、之;(2)从有向图中删去此顶点以及所有以它为尾的弧从有向图中删去此顶点以及所有以它为尾的弧;重复上述两步，直至图空，或者图不空但找不到无重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。前驱的顶点为止。该图的拓扑序列有两个：该图的拓扑序列有两个：（A，B，C，D）（A，C，B，D）一个一个AOV网的拓扑排序序列网的拓扑排序序列是不唯一的。是不唯一的。(a)无环无环AOV网网(b)有环有环AOV网网找不到该网的找不到该网的拓扑有序序列拓扑有序序列练习：练习：对下面的有向图进行拓扑排序，写出所有的对下面的有向图进行拓扑排序，写出所有的拓扑排序序列。拓扑排序序列。u6.5.3关键路径关键路

36、径例：例：设一个工程有设一个工程有 11 项活项活 动，动，9 个事件。个事件。事件事件 v1 表示整个工程表示整个工程 开始（开始（源点源点）事件事件 v9 表示整个工程表示整个工程 结束（结束（汇点汇点）把工程计划表示为有向图，用把工程计划表示为有向图，用顶点顶点表示表示事件事件，弧弧表示表示 活动活动，弧的弧的权权表示表示活动持续时间活动持续时间。每个事件表示在它之前每个事件表示在它之前 的活动已经完成，在它之后的活动可以开始。称这种有向的活动已经完成，在它之后的活动可以开始。称这种有向 图为图为边表示活动的图边表示活动的图，简称为简称为 AOE(Activity On Edge)网网。

37、a8=7a9=4a10=2a11=4a7=9a4=1a5=1a6=2a2=4a1=6v9v8v7v6v4v5v3v2v1a3=5对对AOE网，我们关心两个问题：网，我们关心两个问题：(1)完成整项工程至少需要完成整项工程至少需要 多少时间？多少时间？(2)哪些活动是影响工程进哪些活动是影响工程进哪些活动是影响工程进哪些活动是影响工程进 度的关键？度的关键？度的关键？度的关键？a8=7a9=4a10=2a11=4a7=9a4=1a5=1a6=2a2=4a1=6v9v8v7v6v4v5v3v2v1a3=5路径长度路径长度 路径上各活动持续时间之和路径上各活动持续时间之和。关键路径关键路径 路径长度

38、最长的路径。路径长度最长的路径。ve(j)表示事件表示事件 vj 的最早发生时间。的最早发生时间。vl(j)表示事件表示事件 vj 的最迟发生时间。的最迟发生时间。e(i)表示活动表示活动 ai 的最早开始时间的最早开始时间。l(i)表示活动表示活动 ai 的最迟开始时间。的最迟开始时间。l(i)-e(i)表示完成活动表示完成活动 ai 的时间余量。的时间余量。关键活动关键活动关键活动关键活动 关键路径上的活动，即关键路径上的活动，即 l(i)=e(i)的活动。的活动。ve(3)=4 vl(3)=6 e(5)=4 l(5)=6 l(5)-e(5)=2 如何找如何找 l(i)=e(i)的关键活动

39、？的关键活动？设活动设活动 ai 用弧用弧 表示，其持续时间记为：表示，其持续时间记为：dut()则有则有：(1)e(i)=ve(j)(2)l(i)=vl(k)-dut()(1)从从 ve(1)=0 开始向前递推开始向前递推 (2)从从 vl(n)=ve(n)开始向后递推开始向后递推 如何求如何求 ve(j)和和 vl(j)？a1a2a3a4a5a6a7a8a9a10a11活动活动 e l l e 00645777161400266877101614302023003003求关键路径步骤：求关键路径步骤：求求 ve(i)、vl(j)求求 e(i)、l(i)计算计算 l(i)-e(i)v1v2v

40、3v4v5v6v7v8v9顶点顶点 ve vl 0 6 4 5 7 7161418 0 6 6 8 710161418a8=7a9=4a10=2a11=4a7=9a4=1a5=1a6=2a2=4a1=6v9v8v7v6v4v5v3v2v1a3=5a11=41、若网中有几条关键、若网中有几条关键 路径，则需加快同路径，则需加快同 时在几条关键路径时在几条关键路径 上的关键活动。上的关键活动。如：如：a11、a10、a8、a7。a8=7a10=2a7=9a4=1a1=6a9=4a5=1a6=2a2=4v9v6v4v3a3=5关键路径的讨论关键路径的讨论 2、如果一个活动处于所有的关键路径上，则提高

41、这个活动、如果一个活动处于所有的关键路径上，则提高这个活动 的速度，就能缩短整个工程的完成时间。如：的速度，就能缩短整个工程的完成时间。如：a1、a4。3、处于所有关键路径上的活动完成时间不能缩短太多，否、处于所有关键路径上的活动完成时间不能缩短太多，否 则会使原关键路径变成非关键路径。这时必须重新寻找则会使原关键路径变成非关键路径。这时必须重新寻找 关键路径。如：关键路径。如：a1由由 6 天变成天变成 3 天，就会改变关键路径。天，就会改变关键路径。v8v7v5v2v1a6=10a9=6a10=19a11=4a5=10a4=3a8=13a2=6a1=8v8v7v4v6v5v3v2v1a3=

42、7a7=5a12=2练习练习：如下：如下AOE网，求出各事件的网，求出各事件的ve,vl和各活动和各活动的的l和和e，并求出关键路径。，并求出关键路径。本章小结本章小结 3、邻接表邻接表(Adjacency List)是图的一种顺序存储与链式是图的一种顺序存储与链式存储结合的存储方法。存储结合的存储方法。1、图（、图（Graph）是一种较线性表和树更为复杂的数据）是一种较线性表和树更为复杂的数据结构。而在图形结构中，结构。而在图形结构中，结点之间的关系可以是任意的结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。，图中任意两个数据元素之间都可能相关。2、邻接矩阵邻接矩阵用用一个一个一维数组一维数组存储图中存储图中顶点顶点的信息，一的信息，一个个二维数组二维数组存储存储边边的信息。的信息。4、图的遍历：深度优先搜索和广度优先搜索。、图的遍历：深度优先搜索和广度优先搜索。6、单源点最短路径：迪杰斯特拉算法。、单源点最短路径：迪杰斯特拉算法。5、最小生成树：所有生成树中边的权值之和最小、最小生成树：所有生成树中边的权值之和最小。构。构造最小生成树有普里姆（造最小生成树有普里姆（Prim）算法和克鲁斯卡尔）算法和克鲁斯卡尔（Kruskal）算法。）算法。7、拓扑排序方法及其应用。、拓扑排序方法及其应用。8、关键路径的确定。、关键路径的确定。