数据结构(C语言版)第7章图.ppt

《数据结构(C语言版)第7章图.ppt》由会员分享，可在线阅读，更多相关《数据结构(C语言版)第7章图.ppt（81页珍藏版）》请在三一办公上搜索。

1、图,1、图的基本概念；2、图的存储结构（邻接矩阵、邻接表及有向图十字邻接表）；3、图的遍历（深度优先搜索、广度优先搜索）；4、最小生成树（kruskul算法、prim算法）；5、最短路径（dijkstra算法、floyd算法）；6、AOV网络与拓扑排序；7、AOE网络与关键路径。,教学内容,图的特点,顶点的前驱和后继个数无限制,图的应用,顶点之间的关系是任意的,图中任意两个顶点之间都可能相关,图（Graph）是一种非线性结构。,计算机科学,多对多,7.1 图的定义和术语,定义：,图是一种：数据元素间存在多对多关系的数据结构 加上一组基本操作构成的抽象数据类型。,ADT Graph 数据对象：V

2、 是具有相同特性的数据元素的集合，称为顶点集。数据关系：R=VR VR=|v,wV 且 P(v,w),表示从 v 到 w 的弧，谓词 P(v,w)定义了弧 的意义或信息 基本操作：,定义：,图(Graph)是一种复杂的非线性数据结构，由 顶点集合及顶点间的关系（也称弧或边）集合组成。可以表示为：G(V,VR)其中 V 是顶点的有穷非空集合；VR 是顶点之间关系 的有穷集合，也叫做弧或边集合。弧是顶点的有序对，边是顶点的无序对。,基本操作：,结构初始化CreateGraph(初始条件：V 是图的顶点集，VR 是图中弧的集合。操作结果：按 V 和 VR 的定义构造图 G。,销毁结构DestroyG

3、raph(初始条件：图 G 存在。操作结果：销毁图 G。,引用型操作LocateVex(G,u);初始条件：图 G 存在，u 和 G 中顶点有相同特征。操作结果：若 G 中存在和 u 相同的顶点，则返回该顶点在图 中位置；否则返回其它信息。,GetVex(G,v);初始条件：图 G 存在，v 是 G 中某个顶点。操作结果：返回 v 的值。,FirstAdjVex(G,v);初始条件：图 G 存在，v 是 G 中某个顶点。操作结果：返回 v 的第一个邻接点。若该顶点在 G 中没有邻 接点，则返回“空”。,顶点在图中的“位置”指 的是，在图的存储结构中顶 点之间自然形成的相对位置。,若G，则 称

4、w 为 v 的邻接点，若(v,w)G，则称 w 和 v 互为邻接点。,NextAdjVex(G,v,w);初始条件：图 G 存在，v 是 G 中某个顶点，w 是 v 的邻接顶点。操作结果：返回 v 的（相对于 w 的）下一个邻接点。若 w 是 v 的最后一个邻接点，则返回“空”。,若 v 有多个邻接 点，则在图的存储结 构建立之后，其邻接 点之间的相对次序也 就自然形成了。,加工型操作PutVex(初始条件：图 G 存在，v 是 G 中某个顶点。操作结果：对 v 赋值 value。,InsertVex(初始条件：图 G 存在，v 和图中顶点有相同特征。操作结果：在图 G 中增添新顶点 v。,D

5、eleteVex(初始条件：图 G 存在，v 是 G 中某个顶点。操作结果：删除 G 中顶点 v 及其相关的弧。,InsertArc(初始条件：图 G 存在，v 和 w 是 G 中两个顶点。操作结果：在 G 中增添弧，若 G 是无向的，则还增添 对称弧。,DeleteArc(初始条件：图 G 存在，v 和 w 是 G 中两个顶点。操作结果：在 G 中删除弧，若 G 是无向的，则还删除 对称弧。,DFSTraverse(G,Visit();初始条件：图 G 存在，Visit 是顶点的访问函数。操作结果：对图 G 进行深度优先遍历。遍历过程中对每个顶 点调用函数 Visit 一次且仅一次。一旦 v

6、isit()失败，则操作失败。,BFSTraverse(G,Visit();初始条件：图 G 存在，Visit 是顶点的访问函数。操作结果：对图 G 进行广度优先遍历。遍历过程中对每个顶 点调用函数 Visit 一次且仅一次。一旦 visit()失败，则操作失败。ADT Graph,基本术语：,有向图,无向图,顶点：图中的数据元素。,弧：若 VR，则 表示从 v 到 w 的 一条弧，且称 v 为弧尾，称 w 为弧头，此时的图称 为有向图。,G1=(V1,A1)V1=v1,v2,v3,v4 A1=,边：若 VR 必有VR，则以无序 对(v,w)代表这两个有序对，表示 v 和 w 之间的一条 边，

7、此时的图称为无向图。,G2=(V2,E2)V2=v1,v2,v3,v4,v5 E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),例：两个城市 A 和 B，如果 A 和 B 之间的连线的涵义是表示两 个城市的距离，则 和 是相同的，用(A,B)表示。如果 A 和 B 之间的连线的涵义是表示两城市之间人口流动 的情况，则 和 是不同的。,无向图中边的取值范围：0en(n-1)/2。（用 n 表示图中顶点数目，用 e 表示边的数目。且不 考虑顶点到其自身的边。）,完全图：有 n(n-1)/2 条边的无向图（即：无向图 中每两个顶点之间都存在着一条边

8、)称为完全图。,有向完全图：有 n(n-1)条弧的有向图（即：有向 图中每两个顶点之间都存在着方向相反的两条弧）称 为有向完全图。,有向图中弧的取值范围：0en(n-1)。（用 n 表示图中顶点数目，用 e 表示弧的数目。且不 考虑顶点到其自身的弧。）,稀疏图：含有很少条边或弧的图。,稠密图：含有很多条边或弧的接近完全图的图。,权：与图的边或弧相关的数，这些数可以表示从一个顶点到 另一个顶点的距离或耗费。,网：带权的图。,子图：如果图 G=(V,E)和 G=(V,E)，满足：V V 且 E E，则称 G为G 的子图。,邻接点：若(v,v)是一条边，则称顶点 v 和 v互为邻接点，或称 v 和

9、v相邻接；称边(v,v)依附于顶点 v 和 v，或称(v,v)与顶点 v 和 v 相关联。,若 是一条弧，则称顶点 v 邻接到 v，顶点 v 邻接自 顶点 v。并称弧 与顶点 v 和 v 相关联。,度：无向图中顶点 v 的度是和 v 相关联的边的数目，记为：TD(v)。,入度：有向图中以顶点 v 为头的弧的数目称为 v 的入度，记 为：ID(v)。,出度：有向图中以顶点 v 为尾的弧的数目称为 v 的出度，记 为：OD(v)。,度：入度和出度之和，即：TD(v)=ID(v)+OD(v)。,如果顶点 vi 的度为 TD(vi)，则一个有 n 个顶点 e 条边（弧）的图，满足如下关系：,路径：从顶

10、点 v 到 v 的路径是一个顶点序列(v=vi,0,vi,1,vi,m=v)，满足(vi,j-1,vi,j)VR 或 VR，(1 j m)。,对于有向图，路径也是有向的。,路径长度：路径上边或弧的数目。,回路（环）：第一个顶点和最后一个顶点相同的路径。,简单路径：序列中顶点（两端点除外）不重复出现的路径。,简单回路（简单环）：前后两端点相同的简单路径。,连通：从顶点 v 到 v 有路径，则说 v 和 v 是连通的。,连通图：图中任意两个顶点都是连通的。,非连通图：有 n 个顶点和小于 n-1 条边的图。,连通分量：无向图的极大连通子图（不存在包含它的更大的 连通子图）；任何连通图的连通分量只有

11、一个，即其本身；非连 通图有多个连通分量（非连通图的每一个连通部分）。,强连通图：任意两个顶点都连通的有向图。,强连通分量：有向图的极大强连通子图；任何强连通图的强 连通分量只有一个，即其本身；非强连通图有多个强连通分量。,生成树：所有顶点均由边连接在一起，但不存在回路的图。,一个图可以有许多棵不同的生成树。,注,所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同；生成树是图的极小连通子图；一个有 n 个顶点的连通图的生成树有 n-1 条边；生成树中任意两个顶点间的路径是唯一的；在生成树中再加一条边必然形成回路。,含 n 个顶点 n-1 条边的图不一定是生成树。,生成森林：对于非连

12、通图，其每个连通分量可以构造一棵生 成树，合成起来就是一个生成森林。,有向树：如果一个有向图恰有一个顶点的入度为 0，其余顶 点的入度均为 1，则是一棵有向树。,有向图的生成森林：由若干棵有向树组成，含有图中全部顶 点，但只有足以构成若干棵不相交的有向树的弧。,7.2 图的存储结构,多重链表,7.2.1 数组表示法（邻接矩阵表示法）,对于一个具有 n 个顶点的图，可用两个数组存储。其中一个 一维数组存储数据元素（顶点）的信息，另一个二维数组（图的 邻接矩阵）存储数据元素之间的关系（边或弧）的信息。,邻接矩阵：设 G=(V,VR)是具有 n 个顶点的图，顶点的顺 序依次为 v1,v2,vn，则

13、G 的邻接矩阵是具有如下性质的 n 阶 方阵：,v1 v2 v3 v4,v1 v2 v3 v4 v5,v1 v2 v3 v4,v1 v2 v3 v4 v5,特点：,无向图的邻接矩阵对称，可压缩存储；有 n 个顶点的无向图需 存储空间为 n(n-1)/2。,有向图邻接矩阵不一定对称；有 n 个顶点的有向图需存储空间 为 n，空间复杂度为 O(n2)，用于稀疏图时空间浪费严重。,无向图中顶点 vi 的度 TD(vi)是邻接矩阵中第 i 行 1 的个数。,有向图中,顶点 vi 的出度是邻接矩阵中第 i 行 1 的个数。,顶点 vi 的入度是邻接矩阵中第 i 列 1 的个数。,网的邻接矩阵可定义为：,

14、v1 v2 v3 v4 v5 v6,v1 v2 v3 v4 v5 v6,图的数组（邻接矩阵）存储表示：,#define INFINITY INT_MAX/最大值#define MAX_VERTEX_NUM 20/最大顶点个数 typedef enum DG,DN,AG,AN GraphKind;/有向图,有向网,无向图,无向网 typedef struct ArcCell VRType adj;/VRType是顶点关系类型。对无权图，用 1 或 0 表示相邻否；/对带权图，则为权值类型。InfoType*info;/该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_N

15、UMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;/顶点向量 AdjMatrix arcs;/邻接矩阵 int vexnum,arcnum;/图的当前顶点数和弧(边)数 GraphKind kind;/图的种类标志 MGraph;,7.2.2 邻接表（类似于树的孩子链表表示法）,头结点,表结点,3,1,4,2,0,4,3,1,2,0,2,1,特点：,若无向图中有 n 个顶点、e 条边，则其邻接表需 n 个头结点和 2e 个表结点。适宜存储稀疏图。,无向图中顶点 vi 的度为第 i 个单链表中的结点数。,0,1,2,3,2

16、,1,3,0,v1,v3,v4,v2,邻接表,逆邻接表,顶点 vi 的出度为第 i 个单链 表中的结点个数。,特点：,顶点 vi 的入度为整个单链表 中邻接点域值是 i-1 的结点 个数。,找出度易，找入度难。,找入度易，找出度难。,顶点 vi 的入度为第 i 个单链 表中的结点个数。,顶点 vi 的出度为整个单链表 中邻接点域值是 i-1 的结点 个数。,图的邻接表存储表示：,#define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置 struct ArcNode*nextarc;/指向下一条弧的指针 In

17、foType*info;/该弧相关信息的指针 ArcNode;typedef struct VNode VertexType data;/顶点信息 ArcNode*firstarc;/指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数 int kind;/图的种类标志 ALGraph;,弧结点,7.2.3 十字链表,顶点结点,#define MAX_VERTEX_NUM 20 typedef struct ArcBox int tailvex

18、,headvex;/该弧的尾和头顶点的位置 struct ArcBox*hlink,*tlink;/分别指向下一个弧头相同和弧尾相同的弧的指针域 InfoType*info;/该弧相关信息的指针 ArcBox;typedef struct VexNode VertexType data;ArcBox*firstin,*firstout;/分别指向该顶点第一条入弧和出弧 VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM;/表头向量 int vexnum,arcnum;/有向图的当前顶点数和弧数 OLGraph;,有向图的十字链表存储表示：,7.

19、2.3 邻接多重表（无向图的另一种链式存储结构）,邻接表优点：容易求得顶点和边的信息。缺点：某些操作不方便（如：删除一条边需找表示此 边的两个结点）。,邻接多重表：每条边用一个结点表示。其结点结构如下：,标志域 标记此边是 否被搜索过,标志域 标记此边是 否被搜索过,存与顶点有关的信息,指向第一条依附于该顶点的边,#define MAX_VERTEX_NUM 20 typedef emnu unvisited,visited VisitIf;typedef struct Ebox VisitIf mark;/访问标记 int ivex,jvex;/该边依附的两个顶点的位置 struct EBo

20、x*ilink,*jlink;/分别指向依附这两个顶点的下一条边 InfoType*info;/该边信息指针 EBox;typedef struct VexBox VertexType data;EBox*firstedge;/指向第一条依附该顶点的边 VexBox;typedef struct VexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;/无向图的当前顶点数和边数 AMLGraph;,无向图的邻接多重表存储表示：,7.3 图的遍历,从图的任意指定顶点出发，依照某种规则去访问图中所有顶 点，且每个顶点仅被访问一次，这一过程叫做图的遍历。,

21、图的遍历按照深度优先和广度优先规则去实施，通常有深度 优先遍历法（Depth_First SearchDFS）和 广度优先遍历法（Breadth_Frist SearchBFS）两种。,7.3.1 深度优先遍历（DFS）,方法：1、访问指定的起始顶点；2、若当前访问的顶点的邻接顶点有未被访问的，则任选 一个访问之；反之，退回到最近访问过的顶点；直到 与起始顶点相通的全部顶点都访问完毕；3、若此时图中尚有顶点未被访问，则再选其中一个顶点 作为起始顶点并访问之，转 2；反之，遍历结束。,例：,V1,顶点访问次序：,V2,V4,V8,V5,V3,V6,V7,V1,V2,V5,V8,V4,V3,V6,

22、V7,V1,V2,V4,V8,V5,V3,V7,V6,V1,V2,V5,V8,V4,V3,V7,V6,V1,V3,V6,V7,V2,V4,V8,V5,连通图的深度优先遍历类似于树的先根遍历,a,b,c,h,d,e,k,f,g,a,c,h,d,f,k,e,b,g,顶点访问次序:,例：,a,c,h,d,f,k,e,g,b,a,c,h,f,k,e,d,b,g,解决办法：为每个顶点设立一个“访问标志”。,如何判别V的邻接点是否被访问？,首先将图中每个顶点的访问标志设为 FALSE,之后搜索图 中每个顶点，如果未被访问，则以该顶点为起始点，进行深度 优先遍历，否则继续检查下一顶点。,1,3,7,4,0,

23、V1,V2,V4,V8,V5,V3,实现：,0 1 2 3 4 5 6 7,V1 V2 V3 V4 V5 V6 V7 V8,0 1 2 3 4 5 6 7,2,V6,5,V7,6,1,1,1,1,1,1,1,1,1,3,7,0,V1,V2,V4,V8,V5,V3,0 1 2 3 4 5 6 7,V1 V2 V3 V4 V5 V6 V7 V8,0 1 2 3 4 5 6 7,2,V6,5,V7,6,4,1,1,1,1,1,1,1,1,7.3.2 广度优先遍历（BFS）,方法：从图的某一结点出发，首先依次访问该结点的所有邻 接顶点 Vi1,Vi2,Vin 再按这些顶点被访问的先后次序依次访问 与它

24、们相邻接的所有未被访问的顶点，重复此过程，直至所有顶 点均被访问为止。,例：,广度优先遍历：,V1,V2,V3,V4,V5,V6,V7,V8,V1,V3,V2,V7,V6,V5,V4,V8,V1,V2,V3,V5,V4,V7,V6,V8,a,b,c,h,d,e,k,f,g,a,c,d,e,f,h,k,b,g,顶点访问次序:,例：,a,c,d,e,f,h,k,g,b,1,3,4,0,V1,V2,V3,V4,V5,V6,实现：,0 1 2 3 4 5 6 7,V1 V2 V3 V4 V5 V6 V7 V8,0 1 2 3 4 5 6 7,2,V7,5,V8,6,7,1,1,1,1,1,1,1,1,

25、开始,访问V0，置标志,求V邻接点w,w存在吗,V下一邻接点w,w访问过,结束,N,Y,N,Y,BFS,初始化队列,V0入队,队列空吗,队头V出队,访问w，置标志,w入队,N,Y,7.4 图的连通性问题,7.4.1 无向图的连通分量和生成树,设图 G=(V,E)是个连通图，当从图任一顶点出发遍历图 G 时，将边集 E(G)分成两个集合 T(G)和 B(G)。其中 T(G)是遍历图时所经过的边的集合，B(G)是遍历图时未经过的边 的集合。显然，G1(V,T)是图 G 的极小连通子图。即子图 G1 是连通图 G 的生成树。,深度优先生成树,广度优先生成树,所有顶点均由边 连接在一起，但 不存在回路

26、的图。,深度优先生成森林,一个连通图的生成树不一定是唯一的。,一个非连通图的生成森林不一定是唯一的。,19,17,7.4.3 最小生成树,最小生成树：给定一个无向网络，在该网的所有生成 树中，使得各边权数之和最小的那棵生成树称为该网的最 小生成树，也叫最小代价生成树。,要在 n 个城市间建立通信联络网。顶点：表示城市，权：城市间通信线路的花费代价。希望此通信网花费代价最小。,问题提出：,答案只能从生成树中找，因为要做到任何两个城市之 间有线路可达，通信网必须是连通的；但对长度最小的要求可以 知道网中显然不能有圈，如果有圈，去掉一条边后，并不破坏连 通性，但总代价显然减少了，这与总代价最小的假设

27、是矛盾的。,希望找到一棵生成树，它的每条边上的权值之和（即建立 该通信网所需花费的总代价）最小 最小代价生成树。,问题分析：,结论：,构造最小生成树的算法很多，其中多数算法都利用了一种 称之为 MST 的性质。,MST 性质：设 N=(V,E)是一个连通网，U 是顶点集 V 的一 个非空子集。若边(u,v)是一条具有最小权值的边，其中uU，vV-U，则必存在一棵包含边(u,v)的最小生成树。,N=(V,E),V=v1,v2,v3,v4,v5,v6,E=(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),(v3,v6),(v4,v6),

28、(v5,v6),U=v1,V1,构造最小生成树方法：,方法一：普里姆(Prim)算法。,算法思想：,设 N=(V,E)是连通网，TE 是 N 上 最小生成树中边的集合。,初始令 U=u0,(u0V),TE=。,在所有 uU,vV-U 的边(u,v)E 中，找一条代价最小的边(u0,v0)。,将(u0,v0)并入集合 TE，同时 v0 并入 U。,重复上述操作直至 U=V 为止，则 T=(V,TE)为 N 的最小生 成树。,V1,V3,V6,V4,V2,V5,方法二：克鲁斯卡尔(Kruskal)算法。,算法思想：,设连通网 N=(V,E)，令最小生成树初始状态为只有 n 个顶点而无边的非连通图

29、T=(V,)，每个顶点自成一个连通分量。,在 E 中选取代价最小的边，若该边依附 的顶点落在 T 中不同的连通分量上（即：不能形成环），则将此边加入到 T 中；否 则，舍去此边，选取下一条代价最小的边。,依此类推，直至 T 中所有顶点都在同一 连通分量上为止。,5,最小生成树 可能不惟一,N,T,填空题部分 1.n 个顶点的连通图至少()条边。2.在一个无向图的邻接表中，若表结点的个数是 m，则图中边的 条数是()条。,3.分别用普里姆和克鲁斯卡尔算法构造题图 5-3 所示网络的最小 生成树。,作业：7.1、7.3、7.5、7.7,4.分别求出题图 5-1 从 v2 出发按深度优先搜索和广度优

30、先搜 索算法遍历得到的顶点序列（假设图的存储结构采用邻接矩阵 表示）。5.已知一个有向图的邻接表如题图 5-2 所示，求出根据深度优 先搜索算法从顶点 v1 出发遍历得到的顶点序列。,选择题 1.在一个图中，所有顶点的度数之和等于所有边数的()倍。（A）1/2（B）1（C）2（D）4 2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。（A）1/2（B）1（C）2（D）4 3.一个有 n 个顶点的无向图最多有()条边。（A）n（B）n(n-1)（C）n(n-1)/2（D）2n 4.具有 4 个顶点的无向完全图有()条边。（A）6（B）12（C）16（D）20 5.具有 6 个

31、顶点的无向图至少应有()条边才能确保是一个连通图。（A）5（B）6（C）7（D）86.在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要()条边。（A）n（B）n+1（C）n 1（D）n/2,对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小 为()。（A）n（B）(n-1)2（C）n-1（D）n2 对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则表头数 组的大小为()，所有邻接表中的结点总数是()。（A）n（B）n+1（C）n-1（D）n+e（A）e/2（B）e（C）2e（D）n+e 图的深度优先遍历算法类似于树的（）。（A）先根遍历（B）后根遍历（

32、C）按层遍历图的广度优先遍历算法类似于树的（）。（A）先根遍历（B）后根遍历（C）按层遍历,7.5 有向无环图及其应用,有向无环图：无环的有向图，简称 DAG（Directed Acycline Graph）图。,有向树,有向无环图,有向图,1、描述含有公共子式的表达式：,有向无环图的用途：,共享相同子式 节省存储空间,除最简单的情况之外，几乎所有的工程都可分为若干个称 作“活动”的子工程，并且这些子工程之间通常受着一定条件的 约束，例如：其中某些子工程必须在另一些子工程完成之后才 能开始。,对整个工程和系统，人们关心的是两方面的问题：一是工程能否顺利进行；二是完成整个工程所必须的最短时间。,

33、2、在工程计划和管理方面的应用,对应到有向图即为进行拓扑排序和求关键路径。,7.5.1 拓扑排序,AOV 网：,用一个有向图表示一个工程的各子工程及其相互 制约的关系，其中以顶点表示活动，弧表示活动之间 的优先制约关系，称这种有向图为顶点表示活动的网，简称 AOV(Activity On Vertex network)网。,例：排课表。,C1,C2,C3,C4,C5,C6,C7,C8,C9,C10,C11,C12,若 是网中有向边，则 i 是 j 的直接前驱；j 是 i 的直接后继。,AOV 网中不允许有回路，因为如 果有回路存在，则表明某项活动以 自己为先决条件，显然这是荒谬的。,问题：如何

34、判别 AOV 网中是否存在回路？,AOV 网的特点：,若从 i 到 j 有一条有向路径，则 i 是 j 的前驱；j 是 i 的后继。,拓扑排序：,检测 AOV 网中是否存在环方法：对有向图构造其顶点 的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该 AOV 网必定不存在环。,在 AOV 网没有回路的前提下，我们将全部活动 排列成一个线性序列，使得若 AOV 网中有弧 存在，则在这个序列中，i 一定排在 j 的前面，具有 这种性质的线性序列称为拓扑有序序列，相应的拓扑 有序排序的算法称为拓扑排序。,拓扑排序的方法：,在有向图中选一个没有前驱的顶点且输出之。,从图中删除该顶点和所有以它为

35、尾的弧。,重复上述两步，直至全部顶点均已输出；或者当图中不存在无 前驱的顶点为止,C9,C10,C11,C6,C1,C12,C4,C2,C3,C5,C7,C8,拓扑序列：,C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8,一个AOV网的拓扑序列不是唯一的,例：设一个工程有 11 项活动，9 个事件。事件 v1 表示整个工程 开始（源点）事件 v9 表示整个工程 结束（汇点）,7.5.2 关键路径,把工程计划表示为有向图，用顶点表示事件，弧表示活动，弧的权表示活动持续时间。每个事件表示在它之前的活动已经完 成，在它之后的活动可以开始。称这种有向图为边表示活动的网 络，

36、简称为AOE（Activity On Edge）网。,对于AOE网，我们关心两个问题：(1)完成整项工程至少需要 多少时间？(2)哪些活动是影响工程进 度的关键？,路径长度 路径上各活动持续时间之和。,关键路径 路径长度最长的路径。,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

37、,如何找 l(i)=e(i)的关键活动？,设活动 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)？,求关键路径步骤：求 ve(i)、vl(j)求 e(i)、l(i)计算 l(i)-e(i),0 6 4 5 7 7161418,0 6 6 8 710161418,关键路径的讨论,1、若网中有几条关键路径，则需加快同时在几条关键 路径上的关键活动。如：a11、a10、a8、a7。,2、如果一个活动处于所有的关键路

38、径上，那么提高这个活动的 速度，就能缩短整个工程的完成时间。如：a1、a4。,3、处于所有的关键路径上的活动完成时间不能缩短太多，否则 会使原来的关键路径变成不是关键路径。这时，必须重新寻 找关键路径。如：a1由 6 天变成 3 天，就会改变关键路径。,作业：7.9、7.10,7.6 最短路径,典型用途：交通网络的问题从甲地到乙地之间是否有公 路连通？在有多条通路的情况下，哪一条路最短？,交通网络用有向网来表示：顶点表示城市，弧表示 两个城市有路连通，弧上的权值表示两城市之间的距离、交 通费或途中所花费的时间等。,如何能够使一个城市到另一个城市的运输时间最短或运费最 省？这就是一个求两座城市间

39、的最短路径问题。,问题抽象：在有向网中 A 点（源点）到达 B 点（终点）的 多条路径中，寻找一条各边权值之和最小的路径，即最短路径。,注,最短路径与最小生成树不同，路径上不一定包含 n 个顶点，也不一定包含 n-1 条边。,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：20v1、v4、v2、v5、v7：14 v1、v2、v7：23v1、v4、v2、v7：17v1、v4、v6、v7：24,例：,源点,终点,两种最常见的

40、 最短路径问题,单源点最短路径,所有顶点间的最短路径,从某个源点到其余 各顶点的最短路径,每对顶点间的最短路径,7.6.1 单源点最短路径（从某个源点到其余各顶点的最短路径）,怎样求单源点的最短路径呢?,2、迪杰斯特拉（Dijkstra）算法：按路径长度递增次序产生各顶点的最短路径。,1、将源点到终点的所有路径都列出来，然后在其中选最短的一条。,缺点：当路径特别多时，特别麻烦；没有规律可循。,路径长度最短的最短路径的特点：,在此路径上，必定只含一条弧，且其权值最小。,它只可能有两种情况：1)、直接从源点到 v2（只含一条弧）；,下一条路径长度次短的最短路径的特点：,由此，只要在所有从源点出发的

41、弧中查找权值最小者。,2)、从源点经过顶点 v1，再到达 v2,（由两条弧组成）。,v1 必为已求得的最短路径上的顶点,可能有四种情况：1)、直接从源点到 v3（由一条弧组成）；2)、从源点经过顶点 v1，再到达 v3,（由两条弧组成）；3)、从源点经过顶点 v2，再到达 v3,（由两条弧组成）；4)、从源点经过顶点 v1,v2，再到达 v3,（由三条弧组成）；,再下一条路径长度次短的最短路径的特点：,v1，v2 必为已求得的最短路径上的顶点,其余最短路径的特点：,1)、直接从源点到 vi（只含一条弧）；2)、从源点经过已求得的最短路径上的顶点，再到达 vi（含有多条弧）。,迪杰斯特拉(Dij

42、kstra)算法：按路径长度递增次序产生最短路径,1、把 V 分成两组：(1)S：已求出最短路径的顶点的集合。(2)V-S=T：尚未确定最短路径的顶点集合。2、将 T 中顶点按最短路径递增的次序加入到 S 中，保证：(1)从源点 v0 到 S 中各顶点的最短路径长度都不大于从 v0 到 T 中任何顶点的最短路径长度。(2)每个顶点对应一个距离值：S 中顶点：从 v0 到此顶点的最短路径 长度。T 中顶点：从 v0 到此顶点的只包括 S 中顶点作中间顶点的 最短路径长度。,Dijkstra 算法步骤：,T 中顶点对应的距离值用辅助数组 D 存放。,Di 初值：若 存在，则为其权值；否则为。,v2

43、,1383032,v2,8,13133032,v3,v1,v1,13,13302220,v3,8+5,192220,v4,v4,8+5+6,2120,v6,v5,13+7,21,v5,v6,初始时令 S=v0,T=其余顶点。,v0,从 T 中选取一个其距离值最小的顶点 vj，加入 S。,对 T 中顶点的距离值进行修改：若加进 vj 作中间顶点，从 v0 到 vi 的距离值比 不加 vj 的路径要短，则修改此距离值。,重复上述步骤，直到 S=V 为止。,8+5+6+2,7.6.2 每一对顶点之间的最短路径,方法一：每次以一个顶点为源点，重复执行 Dijkstra 算法 n 次。,若 存在，则存在

44、路径 vi,vj/路径中不含其它顶点 若,存在，则存在路径 vi,v0,vj/路径中所含顶点序号不大于 0 若vi,v1,v1,vj 存在，则存在路径 vi,v1,vj/路径中所含顶点序号不大于 1,方法二：弗洛伊德(Floyd)算法,算法思想：逐个顶点试探，从 vi 到 vj 的所有可能存在的路 径中，选出一条长度最短的路径。,求最短路径步骤：,初始时设置一个 n 阶方 阵，令其对角线元素为 0，若存在弧，则对应元 素为权值；否则为。,逐步试着在原直接路径 中增加中间顶点，若加入中 间顶点后路径变短，则修改 之；否则，维持原值。所有 顶点试探完毕，算法结束。,1、理解图的基本概念，熟悉图的各种存储结构及其 构造方法；2、熟练掌握图的两种遍历方法；3、熟练掌握构造最小生成树的方法，并理解算法；4、掌握求 AOV 网的拓扑排序的方法，并理解算法；5、掌握求解关键路径的方法；6、理解用 Dijkstra 方法求解单源点最短路径问题。,教学要求,作业：7.11、7.13,