数据结构：第七章 图

1、1第七章 图本章目标熟练掌握图中常用的术语和概念。 熟练掌握图的邻接矩阵和邻接表的存储方式。熟练掌握图的深度优先遍历和广度优先遍历的方法和算法。熟练掌握最小生成树的概念和算法。掌握拓扑排序并能求出拓扑序列。掌握关键路径算法并能求出关键路径。7.1 图的抽象数据类型定义7.2 图的存储表示7.3 图的遍历7.4 最小生成树7.7 两点之间的最短路径问题7.5 拓扑排序7.6 关键路径7.1 图的抽象数据类型定义 7.1.1 图的结构定义7.1.2 名词和术语7.1.3 图的基本操作 图是由一个顶点集 V 和一个弧集 VR构成的数据结构。 Graph = (V, VR )其中，VR| v,wV 且

2、 P(v,w) 表示从 v 到 w 的一条弧（一条单向通路），并称 v 为弧尾，w 为弧头。 谓词 P(v,w) 定义了弧 的意义或信息。7.1.1 图的结构定义（V是顶点的有穷非空集合，VR是两顶点间关系的集合。）vw数据元素没有数据元素元素之间的关系线性表元素空表线性关系树结点空树层次关系图顶点不能为空任意顶点都可能存在关系，用边来表示 如“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。EACBD例如:G1 = (V1, VR1)其中V1=A, B, C, D, EVR1=, , , , , , 7.1.2 名词和术语1.有向图： 若VR 必有VR, 即VR是对称的，则以无序对(v

3、,w)代替这两个有序对，称顶点 v 和顶点 w 之间存在一条边(v,w) 。BCAFED由顶点集和边集构成的图称作无向图。例如: G2=(V2,VR2)V2=A, B, C, D, E, FVR2=(A, B), (A, E), (B, E), (B, F), (C, D), (C, F) (D, F)3.边：2.无向图：ABECFAEFBBC设图G=(V, VR) 和 图 G=(V, VR),且 VV, VRVR,则称 G 为 G 的子图。1597211132 弧或边带权的图分别称作有向网或无向网。4. 子图：5. 有向网，无向网：完全图 假设图中有 n 个顶点，e 条边，如果e=n(n-1

4、)/2 ，则该无向图为完全图。有向完全图 将含有 e=n(n-1) 条弧的有向图称作有向完全图。稀疏图： 如果边或弧的个数很少（如满足 e n log n），则称作稀疏图，否则称作稠密图。6. 完全图、稀疏图、稠密图：邻接点：假若顶点v 和顶点w 之间存在一条边， 则称顶点 v 和 w 互为邻接点。例如:TD(B) = 3TD(A) = 2度：与顶点v 关联的边的数目,记为TD(v)。ACDFEB7.邻接点、度对无向图来说，顶点的出度: 以顶点v 为弧尾的弧的数目,记为OD(v);ABECF对有向图来说，顶点的入度: 以顶点v为弧头的弧的数目,记为ID(v)。有向图中顶点的:度(TD)=出度(

5、OD)+入度(ID)例如:I D(B) = 2OD(B) = 1TD(B) = 3由于弧有方向性，则有入度和出度之分8.入度、出度设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR ,1jm,则称从顶点u 到顶点w 之间存在一条路径。路径上边的数目称作路径长度。ABECF 如:从A到F长度为3的路径：简单路径:指序列中顶点不重复出现的路径。简单回路:指序列中第一个顶点和最后一个顶点相同，且除此之外序列中顶点不重复出现的路径。9. 路径、路径长度、简单路径、简单回路ABC ABCFA,B,C,F和 A,E,C,F BCFB练习：24

6、5136路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3157324G26路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1若无向图中任意两个顶点之间都有路径相通，则称此图为连通图;若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。10. 连通图、连通分量BACDFEG1BACDFEG2 若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。ABECFABECF对有向图， 否则，其各个极大强连通子图称作它的强连通分量。

7、11. 强连通图、强连通分量 假设一个连通图有 n 个顶点和 e 条边，其中 n 个顶点和n-1 条边 构成一个极小连通子图，称该极小连通子图为此连通图的生成树。BACDFE12. 生成树 BACDFEBACDFEBACDFE若在一棵生成树上添加一条边，则？。 则必定构成一个环，因为新添加的边必使得依附于这条边的两个顶点之间有了第二条路经。一棵有n个顶点的生成树有且仅有？边若少于n-1条边，则非连通；若多于n-1条边，则必有环。 对非连通图，则称各个连通分量生成树的集合为此非连通图的生成森林。13. 生成森林BAEECDF非连通图BAEECDF生成森林1. 结构的建立和销毁3. 插入或删除顶点

8、5. 对邻接点的操作2. 对顶点的访问操作6. 遍历4. 插入或删除弧7.1.3 图的基本操作CreatGraph(&G, V, VR): / 按定义(V, VR) 构造图DestroyGraph(&G): / 销毁图1. 结构的建立和销毁2. 对顶点的访问操作LocateVex(G, u); / 若G中存在顶点u，则返回该顶点在 / 图中“位置” ；否则返回其它信息。GetVex(G, v); / 返回 v 的值。PutVex(&G, v, value); / 对 v 赋值value。3. 对邻接点的操作FirstAdjVex(G, v); / 返回 v 的“第一个邻接点” 。若该顶点/在

9、G 中没有邻接点，则返回“空”。NextAdjVex(G, v, w); / 返回 v 的（相对于 w 的） “下一个邻接/ 点”。若 w 是 v 的最后一个邻接点，则/ 返回“空”。例NextAdjVex(G, B, E)？FirstAdjVex(G, B) ？邻接点操作与存储表示有关 BACDFEG1234554321AF4. 插入或删除顶点InsertVex(&G, v); /在图G中增添新顶点v。DeleteVex(&G, v); / 删除G中顶点v及其相关的弧。5. 插入或删除弧InsertArc(&G, v, w); / 在G中增添弧，若G是无向的， /则还增添对称弧。Delete

10、Arc(&G, v, w); /在G中删除弧，若G是无向的， /则还删除对称弧。6. 遍 历DFSTraverse(G, v, Visit(); /从顶点v起深度优先遍历图G，并对每个顶点调/用函数Visit一次且仅一次。一旦Visit（）失败，/则操作失败。BFSTraverse(G, v, Visit(); /从顶点v起广度优先遍历图G，并对每个顶点调/用函数Visit一次且仅一次。一旦Visit（）失败，/则操作失败。7.1 图的抽象数据类型定义7.2 图的存储表示7.3 图的遍历7.4 最小生成树7.7 两点之间的最短路径问题7.5 拓扑排序7.6 关键路径7.2 图的存储表示图的存储

11、结构必须反映出图的一些基本特征： * 图的种类（有向图、有向网、无向图、无向网） * 图的顶点数和图的边数 * 边的信息 （邻接点、权、含义） * 顶点的信息 （编号、名称、含义）因此，设计图的存储结构必须对上述各项进行描述。 7.2 图的存储表示7.2.1 图的数组(邻接矩阵)存储表示7.2.2 图的邻接表存储表示7.2.3 有向图的十字链表存储表示 图的存储表示的特点： 图结构中任意两个顶点之间都可能存在“关系”，因此无法以顺序存储映象表示这种关系，即图没有顺序存储结构 。 7.2 图的存储表示顶点表: 一个记录各个顶点信息的一维数组，邻接矩阵：一个表示各个顶点之间的关系（边或弧）的二维数

12、组。设图 G = (V, E)是一个有 n 个顶点的图，则图的邻接矩阵G.arcsnn 定义为：G.arcsij= 1 若 或(Vi,Vj)E 0 反之7.2.1邻接矩阵 (Adjacency Matrix)表示法（数组表示法）Aij= 0 , (vi,vj)VR 1 , (vi,vj)VR7.2.1 图的数组(邻接矩阵)存储表示定义: nn矩阵的元素为 1 2 3 4 5 6123456V1V2V3V4V5V6无向图网的邻接矩阵存储表示定义: nn矩阵的元素为无向网V1V2V3V4V5V615671122512 1 2 3 4 5 6123456888888888888888888888 A

13、ij= wi,j ,(vi,vj) VR ,(vi,vj) VR8显然，无向图和无向网的邻接矩阵是对称矩阵。有向图的邻接矩阵为非对称矩阵V1V2V4V3V5 1 2 3 4 512345出度？入度？出度入度 typedef struct / 图的定义 MGraph;typedef struct ArcCell / 弧的定义 VRType adj; / VRType是顶点关系类型。 / 对无权图，用1或0表示相邻否； / 对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;

14、 VertexType vexsMAX_VERTEX_NUM; / 顶点向量，顶点信息 AdjMatrix arcs; / 邻接矩阵 ，弧信息 int vexnum, arcnum; / 顶点数，弧数 GraphKind kind; / 图的种类标志 (DG,UDG,DN,UDN) 采用邻接矩阵构造无向图输入：图的顶点数vexnum, 边数arcnum，边信息指针info图的顶点向量（V1, V2, , Vn )图的边信息（V1, V2 ) 及权值W输出： 邻接矩阵AdjMatrixvexnumvexnum 顶点向量 vexsvexnumStatus CreateUDN (Mgraph &G)

15、 /构造无向图 scanf(&G.vexnum,&G.arcnum,&IncInfo) /输入顶点数，边数 for(i=0;i G.vexnum;+i) scanf(&G.vexsi); /输入顶点向量 for(i=0;i G.vexnum;+i) /初始化邻接矩阵 for(j=0;j G.vexnum;+j) G.arcsij=0,NULL; for(k=0;k G.arcnum;+k) /构造邻接矩阵 scanf(&v1,&v2); /输入一条边依附的顶点 i=LocateVex(G,v1); j= LocateVex(G,v2); /定位v1, v2 G.arcsij.adj=1; /弧

16、的邻接关系 if(IncInfo) Input (*G.); 输入边相关信息 G.arcsji= G.arcsij; /置邻接矩阵对称值 /IncInfo为0表示各弧不含其它信息7.2.2邻接表及其实现 用邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，而与边的数目无关。一个含有n个顶点的图，如果其边数比n2少得多，那么它的邻接矩阵就会有很多空元素，浪费了存储空间。 邻接表 对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表。单链表中的每个结点至少包含两个域，一个为邻接点域（adjvex），

17、它指示与顶点vi邻接的顶点在图中的位序，另一个为链域（next），它指示与顶点vi邻接的下一个结点。 adjvex nextarc data firstarc 为了便于随机访问任一顶点的邻接表，可将所有头结点顺序存储在一个向量中就构成了图的邻接表存储。最后将图的顶点数及边数等信息与邻接表放在一起来描述图的存储结构。 v0v1v3v2 无向图1 2 3 0 2 0 1 3 0 2 V0V1V2V3邻接表表头结点结构边结点结构 对于无向图，vi的邻接表中每个表结点都对应于与vi相关联的一条边；对于有向图来说，如果每一顶点vi的邻接表中每个表结点都存储以vi的为始点射出的一条边，则称这种表为有向图的

18、出边表（有向图的邻接表），反之，若每一顶点vi的邻接表中每个表结点都对应于以vi为终点的边（即射入vi的边），则称这种表为有向图的入边表（又称逆邻接表）。 v0v1v2v31 0 2 0 1 1 出边表v0v1v2v3 1 2 0 2 1 3 入边表v3v1v0v2 有向图 在无向图的邻接表中，顶点vi的度为第i个链表中结点的个数；而在有向图的出边表中，第i个链表中的结点个数是顶点vi的出度；为了求入度，必须对整个邻接表扫描一遍，所有链表中其邻接点域的值为i的结点的个数是顶点vi的入度。 1 2 3 0 2 0 1 3 0 2 V0V1V2V3V0的度为3v0v1v2v31 0 2 0 1 1

19、 有向图出边表V0的出度为1，入度为2 无向图网络 (带权图) 的邻接表typedef struct AdjList vertices; /顶点向量 int vexnum, arcnum; / 图的当前顶点数和弧数 int kind; / 图的种类标志 ALGraph;图的结构定义(邻接表)typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; data firstarc顶点的结点结构typedef struct ArcNode in

20、t adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode;adjvex nextarc info弧的结点结构ABECD构造有向图的邻接表算法230 12 A B C D E4 输入顶点数和弧数输入顶点表头向量输入弧产生一个新的弧结点定位弧的顶点v1和v2对新弧结点赋值插入弧结点到单链表0, 1114 01234练习：1.画出有向图G的邻接矩阵、邻接表、逆邻接表。V1V3V4V5V6V2G邻接表 逆邻接表 1 50 42 31 v1 v2 v3 v4 v5 v6

21、01234552 50 31 35 v1 v2 v3 v4 v5 v62012345课堂练习：1 对于下列无向图，试给出（1）图中每个顶点的度；（2）该图的邻接矩阵；（4）该图的连通分量。v0v3v4v2v1v5v62 给定有向图，试给出（1）顶点D的入度与出度；（2）该图的邻接表(出边表)与逆邻接表(入边表)；（3）该图的强连通分量。 ABCDE将有向图的邻接表和逆邻接表合起来将有向图的邻接表和逆邻接表合起来三部分：顶点的结点结构弧的结点结构图的结构定义7.2.3 有向图的十字链表存储表示 ABECD1 4230 120 1 2 3 4 A B C D E 邻接表 逆邻接表 A B C D

22、E 3 0 3 4 2 0012341顶点的结点结构顶点信息数据 指向该顶点的第一条入弧指向该顶点的第一条出弧typedef struct VexNode / 顶点的结构表示 VertexType data; ArcBox *firstin, *firstout; VexNode;datafirstinfirstout弧的结点结构弧尾顶点位置 弧头顶点位置 弧的相关信息指向下一个有相同弧尾的结点指向下一个有相同弧头的结点typedef struct ArcBox / 弧的结构表示 int tailvex, headvex; InfoType *info; struct ArcBox *hlin

23、k, *tlink; ArcBox ;hlinktlinktailvexheadvexinfotypedef struct VexNode xlistMAX_VERTEX_NUM; / 顶点结点(表头向量) int vexnum, arcnum; /有向图的当前顶点数和弧数 OLGraph;图的结构定义2 33 13 03 22 00 10 2V1V2V3V40123例如： v1v4v2v301231 0若增加一条边练习：画出有向图G的十字链表。V1V3V5V4V2G2 13 00 1V1V2V3V4V5012341 21 32 33 4出链入链7.3 图的遍历树的遍历： 从根开始遍历； 遍历

24、可以从左到右，从上到下； 存储结构不改变遍历结果；深度优先搜索DFS (Depth_First Search)广度优先搜索BFS(Breadth_First Search)图的遍历: 从图中某一顶点出发遍历图中其余顶点， 使得每个结点均被访问一次，而且仅被访问一次。 从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。7.3.1、深度优先搜索连通图的深度优先搜索遍历1. 访问顶点 V ;2. for (W1、W2、W3 ) 若该邻接点Wi未被访问， 则深度优先搜索遍历该子图。1. 访问根结点；2. 先序

25、遍历左子树；3. 先序遍历右子树。二叉树的先根遍历图的深度优先遍历根左子树右子树根左子树右子树子图3子图1子图2Vw1w3w2w1w2w3深度优先搜索DFS ( Depth First Search )深度优先搜索的示例 DFS 的思路（1）从图中的某个顶点V出发，访问之；（2）依次从顶点V的未被访问过的邻接点出发， 深度优先遍历图，直到图中所有和顶点V 有路径相通的顶点都被访问到；（3）若此时图中尚有顶点未被访问到，则另选 一个未被访问过的顶点作起始点，重复上 述（1）（2）的操作，直到图中所有的顶 点都被访问到为止。深度优先搜索举例:BACDFE从B点开始遍历BAEFDC深度优先搜索举例:

26、BACDFE从B点开始遍历.BEAFCDBAEFDC由于没有规定访问邻接点的顺序，深度优先序列不是唯一的c0c1c3c2c4c5c0c1c3c2c4c5DFS序列：c0 c1 c3 c4 c5 c2 但是，在存储结构和源点已确定的情况下，遍历的结果将是确定的。深度优先搜索遍历归纳:深度优先搜索遍历连通图的过程类似于树的先根遍历;3. 解决的办法是:为每个顶点设立一个 “访问标志 visitedw”;2. 遍历过程需要判别V的邻接点是否被访问？void DFS(Graph G, int v) / 从顶点v出发，深度优先搜索遍历连通图 G visitedv = TRUE; VisitFunc(v)

27、; for(w=FirstAdjVex(G, v); w=0;w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 对v的尚未访问的邻接顶点w / 递归调用DFS / DFS深度优先搜索遍历算法: 1 2 3 4 5 6123456基于邻接矩阵的深度优先搜索举例从B点开始遍历 visited 0, 0, 0, 0, 0, 0 邻接矩阵DBACFEBAEFCD顶点向量 A, B, C, D, E, F void DFS_M(MGraph G, int i, int n) / 从顶点Vi出发，深度优先搜索遍历邻接矩阵图 G visitedi = TRUE;

28、 /标记Vi已被访问过 printf(G.vexsi) ; /输出Vi for(j=0; jadjvex； if (! visitedj ) /若Vj未被访问过，则递归调用 DFS _AL(G, j, n); p=p- nextarc; /使p指向vi单链表的下一个邻接点 /while / DFS _AL基于邻接表的深度优先搜索算法 首先将图中每个顶点的访问标志设为 FALSE，之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。非连通图的深度优先搜索遍历F F F F F F F F F0 1 2 3 4 5 6 7 8abchdekfgTTT

29、TTTTTTachdkfe bgachkfedbg访问标志:访问次序:例如:812345670 从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。7.3.2 广度优先搜索广度优先搜索的示例 广度优先搜索过程 广度优先生成树 广度优先搜索算法的思路（1）从图中的某个顶点V出发，访问之；（2）依次访问顶点V的各个未被访问过的邻接 点，将V的全部邻接点都访问到；（3）分别从这些邻接点出发，依次访问它们的 未被访问过的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶

30、点的邻接点”被访问，直到图中所有已被访问过的顶点的邻接点都被访问到。广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。QUEUEV0V1V2V3V4V5V6V7V1V2V3V0V4V5V6V7 V0 V7 V6 V5 V4 V3 V2 V1AB FF C I GC I G EI G E DG E DE D HD HH入列出列void BFSTraverse(Graph G, int v )

31、for (v=0;vG.vexnum;+v) visitedv=FALSE; InitQueue(Q); for (v=0;v=0; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw=TRUE; printf(w); EnQueue(Q, w); / 访问的顶点w入队列 / if / while /if /BFSTraverse7.4 最小生成树7.4.1 连通图的生成树7.4.2 连通网的最小生成树 对于一个连通图G=（V，E），设G是它的一个子图，如果G中包含了G中所有的顶点（即V（G）=V（G）且G是无回路的连通图，则称G为G一棵的生成树。 7.

32、4.1 连通图的生成树 一个连通图可以有多棵生成树：从不同的顶点出发得到不同的生成树； 采用不同的搜索方法得到不同的生成树；采用不同的存储结构得到不同的生成树；深度优先生成树（DFS生成树） 由深度优先搜索得到的生成树；广度优先生成树（BFS生成树） 由广度优先搜索得到的生成树。例7.4.1:画出下面有向图从顶点v1开始的DFS生成树与BFS生成树。V2V4V5V3V7V6V1V2V4V5V3V7V6V1V2V4V5V3V7V6V1DFS生成树BFS生成树练习：画出下面非连通图从顶点v1开始的DFS与BFS生成森林。V2V4V5V3V7V6V1V8V2V4V5V3V7V6V1V8DFS生成森林

33、V2V4V5V3V7V6V1V8BFS生成森林 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？问题：7.4.2 连通网的最小代价生成树北京济南郑州青岛广州大连7131791812752410顶点表示城市权值城市间建立通信线路所需花费代价 希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小-最小代价生成树。 构造网的一棵最小代价生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”最小。算法二：克鲁斯卡尔(Kruskal)算法该问题等价于：算法一：普里姆(Prim

34、)算法 构造最小生成树可以有多种算法，其中大多数算法都是利用了最小生成树的下述性质： 设G(V，E)是一个连通网，U是顶点集V的一个非空真子集。若(u，v)是满足uU，vV-U的边（称这种边为两栖边）且(u，v)在所有两栖边中具有最小权值，则一定存在G的一棵最小生成树包含此边(u，v)。这个性质称为MST性质。 (Minimum Cost Spanning Tree)abcdegf195141827168213127U= , abV-U= , , , , efdcg一、普里姆(Prim)算法的基本思想是： 首先从V中任取一个顶点u0，将生成树T置为仅有一个结点u0的树，即置Uu0；然后只要U是

35、V的真子集，就在所有两栖边中，找一条权值最小的边(u，v)，并把该条边(u，v)并入T的边集、其不在T中的顶点v并入顶点集U中。如此进行下去，每次往生成树里并入一个顶点和一条边，直到把所有顶点都包括进生成树T为止。此时，必有UV，TE中有n-1条边。MST性质保证上述过程求得的T(U，TE)是G的一棵最小生成树。 v1v2v3vkvnv0原图顶点集合V-Uv0v196156915720vk7最小生成树顶点集合U92025普里姆(Prim)算法：利用普里姆算法建立最小生成树ABCDEF10101512128765 （a）无向网5ABCDEF107610（e）选取（B、F）ABCDEF101512

36、（b）初始状态5ABCDEF101576（c）选取（A、B）5ABCDEF101576（d）选取（B、D） 5ABCDEF107610（f）选取（B、C）5ABCDEF107610（g）选取（E、F）16abcdegf195141827168213127例如:aedcbgf148531621所得生成树权值和= 14+8+3+5+16+21 = 67 假设在生成树的构造过程中，图中 n 个顶点分属两个集合：落在生成树上的顶点集 U 和尚未落在生成树上的顶点集 V-U 。 下一步应该在所有连通U中和V-U中的顶点的边（两栖边）中，选取权值最小的边。V-U U普里姆算法的关键:struct Vert

37、exType adjvex; / 顶点 VRType lowcost; / 权值 closedgeMAX_VERTEX_NUM; 设置一个辅助数组，以记录从U到VU具有最小代价的边。对每个顶点vi VU在辅助数组存在一个相应的分量closedgei-1，它包括两个域：普里姆算法的实现：每个顶点有一个closedgei值，其分量.lowcost：从U中任一顶点到该顶点(由i确定)权值的最小值；.adjvex：依附于这条最小代价边的另一个顶点。.lowcost= 0 表示顶点i已在U中； 0 表示顶点i还在V-U中。 所以，每次循环须在.lowcost 0(在集合V-U中)的那些顶点中选择.low

38、cost 最小的顶点加入到集合U中，同时将相关顶点的closedge作相应的调整。普里姆算法的实现：abcdegf195141827168213127aedb基于邻接矩阵的 普里姆算法0 1 2 3 4 5 6ca19aaaaaa141888800gf12e8e16e03d21d7d5c0000191418195712537382114128162127181627a b c d e f gabcdefg 普里姆算法归纳(基于邻接矩阵存储结构)： 1. 根据起始顶点初始化辅助数组；2. 起始顶点lowcost值置0 ；3.循环处理其余n-1个顶点； 求剩余顶点中lowcost值最小的顶点k;

39、输出顶点k和边作为生成树的一个结点和边； 将第k 个顶点的lowcost置0，表示加入U集； 循环将新顶点并入U集后重新选择最小边；void MiniSpanTree_P(MGraph G, VertexType u) /用普里姆算法从顶点u出发构造网G的最小生成树 k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 辅助数组初始化 if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / 初始化，Uu for (i=1; iG.vexnum; +i) ?继续向生成树上

40、添加顶点;见下页。 k = minimum(closedge); / 求出加入生成树的下一个顶点(k) printf(closedgek.adjvex, G.vexsk); / 输出生成树上一条边 closedgek.lowcost = 0;/将第k 顶点置0，表示加入U集； for (j=0; jG.vexnum; +j) /循环将新顶点并入U集以便重新选择最小边； if (G.arcskj closedgej.lowcost) closedgej = G.vexsk, G.arcskj ; 考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。二、克

41、鲁斯卡尔(Kruskal)算法的基本思想：克鲁斯卡尔(Kruskal)算法具体做法: 假设图G（V，E）是一个连通图； 先构造一个只含 n 个顶点且无边的非连通图T（V， ），图中每个顶点自成一个连通分量； 从图G中选择权值最小的边，如果该边的两个顶点落在图T的不同连通分量上，则将该边加入到T中，否则选择下一条边； 如此重复，直至加上 n-1 条边为止。251234192646381725ABEDCFABEDCF连通分量A, B, C, D, E, F最小生成树算法 Kruskal算法251234192646381725ABEDCFABEDCF连通分量A, B, C, D, E, F12连通分

42、量A, B, E, C, D, F 最小生成树算法 Kruskal算法251234192646381725ABEDCFABEDCF连通分量A, B, E, C, D, F12连通分量A, B, E, C, D,F174 最小生成树算法 Kruskal算法251234192646381725ABEDCFABEDCF连通分量A, B, E, C, D, F12连通分量A, F, B, E, C, D1917最小生成树算法 Kruskal算法251234192646381725ABEDCFABEDCF连通分量A, F, B, E, C, D12连通分量A, F, C, D, B, E191725最小

43、生成树算法 Kruskal算法251234192646381725ABEDCFABEDCF连通分量A, F, C, D, B, E12连通分量A, F, C, D, B, E19172526最小生成树算法 Kruskal算法1. 初始化：U=V； TE= ； 2. 循环直到T中的连通分量个数为1 2.1 在E中寻找最短边(u，v); 2.2 如果顶点u、v位于T的两个不同连通分量，则 2.2.1 将边(u，v)并入TE； 2.2.2 将这两个连通分量合为一个； 2.3 在E中标记边(u，v)，使得(u，v)不参加后续最短边的选取；Kruskal算法的基本步骤如下：应用克鲁斯卡尔算法构造最小生成

44、树的过程例:5148213aedcbgfabcdegf19514627168213ae12dcbgf76 Prim 算法：初始值为某个顶点(即1个连通分量)，在一个连通分量上添加边和顶点。 Kruskal 算法：初始值为n个顶点(即n个连通分量)，每次使连通分量的个数减一。 用一句话描述两种算法练习：利用Prim算法、Kruskal算法构造最小生成树。gde afcbh21112221234gde afcbh2111221结果：7.1 图的抽象数据类型定义7.2 图的存储表示7.3 图的遍历7.4 最小生成树7.7 两点之间的最短路径问题7.5 .1拓扑排序7.5.2关键路径7.5 有向无环图

45、及其应用 有向无环图（directed acycline graph）：无环的有向图，简称DAG图。DAG图是一类较有向树更一般的特殊有向图。 图7.21 有向树、DAG图和有向图一例例如，图7.21示例了有向树、DAG图和有向图的例子。有向无环图是描述含有公共子式的表达式的有效工具 例如，下述表达式(a +b ) * (b * (c + d) + (c + d) * e) * (c + d) * e)，用二叉树表示如图7.22所示，用有向无环图表示如图7.23所示。 图7.22 用二叉树描述表达式*+*+e+*abbcc d dec d图7.23 描述表达式的有向无环图*+eabc d*+*

46、+*表达式(a +b ) * (b * (c + d) + (c + d) * e) * (c + d) * e)有向无环图也是描述一项工程或系统进行过程的有效工具对整个工程和系统，人们关心的是两个方面的问题：（1）工程能否顺利进行；（2）估算整个工程完成所必须的最短时间 ；对应于有向图，即为进行拓扑排序和求关键路径的操作。 7.5.1 AOV网与拓扑排序什么是AOV网？AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。编号课程名称先修课C1高等数学无C2计算机导论无C3离散数学C1C4程序设计C1, C2C5数据结

47、构C3，C4C6计算机原理C2，C4C7数据库原理C4，C5，C6C1C2C3C4C6C5C7AOV网图1 软件专业的学生必须学习的课程图 2 表示课程之间优先关系的有向图AOV网特点：1.AOV网中的弧表示活动之间存在的某种制约关系。2.AOV网中不能出现回路 。拓扑排序拓扑序列：设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1, v2, , vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。拓扑排序：对一个有向图构造拓扑序列的过程称为拓扑排序 。拓扑排序基本思想： 从AOV网中选择一个没有前驱的顶点并且输出； 从

48、AOV网中删去该顶点，并且删去所有以该顶点为尾的弧； 重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。C1C2C3C4C6C5C7拓扑序列：C1, 拓扑排序C2C3C4C6C5C7拓扑序列：C1, C2, 拓扑排序C3C4C6C5C7拓扑序列：C1, C2, C3, 拓扑排序C4C6C5C7拓扑序列：C1, C2, C3, C4, 拓扑排序C6C5C7拓扑序列：C1, C2, C3, C4, C5, 拓扑排序C6C7拓扑序列：C1, C2, C3, C4, C5, C6, 拓扑排序C7拓扑序列：C1, C2, C3, C4, C5, C6, C7, 拓扑排序设计数据结构1

49、. 图的存储结构：（删除顶点）宜采用邻接表存储 。2. 为便于算法执行过程中考察的入度为0的顶点，可引入一个存放各顶点入度的数组indegree。3. 为了避免每一步选入度为0的顶点时重复扫描数组indegree，可设置一个栈（或队列）来存储所有入度为0的顶点。在进行拓扑排序之前，只要对顶点表扫描一遍，将所有入度为0 的顶点都推入栈中，一旦排序过程中出现新的入度为0的顶点，也同样将其推入栈中。 (a) 一个AOV网 (b) AOV网的邻接表存储 012345 in vertex firstedge3 A 0 B1 C3 D0 E2 F 0 3 0 0 5 2 3 3 5 ABCDEF拓扑排序0

50、12345 in vertex firstedge 3 A 0 B 1 C 3 D 0 E 2 F 0 3 0 0 5 2 3 3 5 ABCDEFBE拓扑排序012345 in vertex firstedge 3 A 0 B 1 C 3 D 0 E 2 F 0 3 0 0 5 2 3 3 5 ABCDEFBE0C21拓扑排序012345 in vertex firstedge 3 A 0 B 0 C 2 D 0 E 1 F 0 3 0 0 5 2 3 3 5 ABCDFBC21拓扑排序012345 in vertex firstedge 2 A 0 B 0 C 1 D 0 E 1 F 0

51、3 0 0 5 2 3 3 5 ABDFBD01拓扑排序012345 in vertex firstedge 1 A 0 B 0 C 0 D 0 E 1 F 0 3 0 0 5 2 3 3 5 ADF00AF拓扑排序012345 in vertex firstedge 0 A 0 B 0 C 0 D 0 E 0 F 0 3 0 0 5 2 3 3 5 AFAF拓扑排序1. 栈S初始化；累加器count初始化；2. 扫描顶点表，将没有前驱的顶点压栈；3. 当栈S非空时循环 3.1 vj=退出栈顶元素；输出vj；累加器加1； 3.2 将顶点vj的各个邻接点的入度减1； 3.3 将新的入度为0的顶点

52、入栈；4. if (countvertexNum) 输出有回路信息；拓扑排序算法伪代码拓扑排序解决的是工程能否顺利完成，但有时候需要解决最短时间完成7.1 图的抽象数据类型定义7.2 图的存储表示7.3 图的遍历7.4 最小生成树7.6 两点之间的最短路径问题7.5.1 拓扑排序7.5.2 关键路径7.5.2 AOE网与关键路径 AOE-网（Activity On Edge）：即边表示活动的网。AOE-网是一个带权的有向无环图。其中，顶点表示事件（Event），弧表示活动，权表示活动持续的时间。（1）AOE-网事件 事件含义 v1 开工 v2 活动a1完成，活动a4可以开始 v3 活动a2完成

53、，活动a5可以开始 v9 活动a10 和a11完成，整个工程完成v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=47.5.2 AOE网与关键路径 图7.29源点汇点AOE网可以回答下列问题：1. 完成整个工程至少需要多少时间?2. 为缩短完成工程所需的时间, 应当加快哪些活动?从始点到终点的路径可能不止一条，只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的最短时间取决于从始点到终点的最长路径长度，即这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径。7.5.2 AOE网与

54、关键路径 （2）关键路径：在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。关键活动：关键路径上的活动称为关键活动。由于AOE网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期。7.5.2 AOE网与关键路径 要找出关键路径，必须找出关键活动, 即不按期完成就会影响整个工程完成的活动。首先计算以下与关键活动有关的量：事件（顶点）的最早发生时间vek 事件（顶点）的最迟发生时间vlk 活动（弧）的最早开始时间ei 活动（弧）的最晚开始时间li最后计算各个活动的时间余量 l

55、k - ek，时间余量为0者即为关键活动。7.5.2 AOE网与关键路径 vek是指从始点开始到顶点vk的最大路径长度。这个长度决定了所有从顶点vk发出的活动能够开工的最早时间。 ve1=0vek=maxvej+len (pk) pk表示所有到达vk的有向边的集合 事件的最早发生时间vek vjvkv2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4v2v7v6v5v4v1v3v9v8vek064577161418vek=maxvej+len应用举例关键路径 vlk是指在不推迟整个工期的前提下,事件vk允许的最晚发生时

56、间。 事件的最迟发生时间vlk vjvjvkvln=venvlk=minvlj-len（sk）sk为所有从vk发出的有向边的集合v2v7v6v5v4v1v3v9v8vekvlk0645771614181814161078660v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4应用举例关键路径vlk=minvlj-len 活动的最早开始时间ei 若活动ai是由弧表示，则活动ai的最早开始时间应等于事件vk的最早发生时间。因此，有： ei=vek v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a1

57、1=4a8=7a9=4a5=1a6=2a3=5a2=4v2v7v6v5v4v1v3v9v8vek064577161418a2a7a6a5a4a1a3a9a8ei000645777a10a111614ei=vek 应用举例关键路径 活动ai的最晚开始时间是指，在不推迟整个工期的前提下， ai必须开始的最晚时间。 若ai由弧表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此，有： li=vlj-len 活动的最晚开始时间lili10778663201614v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4

58、a2a7a6a5a4a1a3a9a8a10a11v2v7v6v5v4v1v3v9v8vlk1814161078660li=vlj-len 应用举例关键路径a2a7a6a5a4a1a3a9a8eili0006457771077866320a10a1116141614v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4关键活动：li=ei的活动应用举例关键路径求关键路径步骤求ve(i)求vl(j)求 e(i)求 l(i)计算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9

59、a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点 ve vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动 e l l-e00002266046258377077071031616014140033abcdefghp6452118724400000000064571157151418181818181818181818161486610807拓扑有序序列: a - d - f - c - b - e - h - g - pp算法的执行过程 算法的实现要点:显然，求ve的顺序应该是按拓扑序列的顺序;而求vl的顺序应该是按

60、拓扑序列的逆序;因此应该在拓扑排序的过程中， 另设一个“栈”记下拓扑序列。例：对如下AOE网，求出各活动的最早开始时间e(i)和最迟开始时间l(i)。问：工程完成的最短时间是多少？哪些活动是关键活动？并画出关键路径。v1v2v10v9v8v7v6v5v4v3a1=5a2=6a8=5a3=3a5=3a4=6a9=1a12=5a10=4a13 =2a11=4a7=4a6 =3a14=2v1v2v10v9v8v7v6v5v4v3a1=5a2=6a8=5a3=3a5=3a4=6a9=1a12=5a10=4a13 =2a11=4a7=4a6 =3a14=2答：v1v10v9v7v4v3活动a1a2a3a