数据结构 第七章 图

1、1第七章第七章 图图 设某田径比赛共有设某田径比赛共有六六个比赛项目，规定每个选手个比赛项目，规定每个选手至多可参加至多可参加三三个项目，有个项目，有五五人报名参加比赛（如下表人报名参加比赛（如下表所示）。设计比赛日程表，使得比赛能在尽可能短的所示）。设计比赛日程表，使得比赛能在尽可能短的时间内完成。时间内完成。引入：引入：田径田径比赛的时间安排问题比赛的时间安排问题 （1 1）设用如下六个不同的代号代表不同的项目：）设用如下六个不同的代号代表不同的项目： （2 2）用顶点代表比赛项目）用顶点代表比赛项目 （3 3）在）在不能同时进行比赛不能同时进行比赛的顶点之间连上一条边的顶点之间连上一条边

2、 （4 4）给顶点涂色：任何有边相连的顶点不能涂）给顶点涂色：任何有边相连的顶点不能涂 同一种颜色，且使涂色数目尽量少同一种颜色，且使涂色数目尽量少姓名姓名项目项目1 1项目项目2 2项目项目3 3丁一丁一 A B E赵二赵二 C D 张三张三 C E F李四李四 D F A王五王五 B FAEBFDC比赛时间比赛项目1A，C2B，D3E4F 只需安排四个单位时间进行比赛AEBFDC图本章目标本章目标n熟练掌握图中常用的术语和概念。 n熟练掌握图的邻接矩阵和邻接表的存储方式。n熟练掌握图的深度优先遍历和广度优先遍历的方法和算法。n熟练掌握最小生成树的概念和算法。n掌握拓扑排序并能求出拓扑序列。

3、n掌握关键路径算法并能求出关键路径。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 且 P(v,w) 表示

4、从 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.1.有向图：有向图： 若VR 必有VR, 即VR是对称对称的，则以无序对无序对(v,w)代替这两个有序对，称顶点 v 和顶点 w 之间存在一条边(

5、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.3.边：边：2.2.无向图：无向图：ABECFAEFBBC设图G=(V, VR) 和 图 G =(V, VR),且 VV, VRVR,则称 G 为 G 的子图子图。1597211132 弧或边带权的图分别称作有向网或无向网。4. 子图子图：5. 有向网，无向网有向网，无向网：完全图完全图 假设图中有 n 个顶点，e 条边，如果e=n(n-1)/

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

7、点v 为弧尾的弧的数目,记为OD(v);ABECF对有向图来说对有向图来说，顶点的入度入度: : 以顶点v为弧头的弧的数目,记为ID(v)。有向图中顶点的有向图中顶点的: :度度( (TD)=)=出度出度( (OD)+)+入度入度( (ID) )例如例如: :I D(B) = 2OD(B) = 1TD(B) = 3由于弧有方向性，则有入度入度和出度出度之分8.8.入度、出度入度、出度设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR ,1jm,则称从顶点u 到顶点w 之间存在一条路径路径。路径上边的数目称作路径长度路径长度。ABE

8、CF 如如: :从A到F长度为3的路径：简单路径简单路径:指序列中顶点不重复出现的路径。简单回路简单回路:指序列中第一个顶点和最后一个顶点相同，且除此之外序列中顶点不重复出现的路径。9. 路径、路径长度、简单路径、简单回路路径、路径长度、简单路径、简单回路ABC ABCFA,B,C,F和 A,E,C,F BCFB练习：练习：245136路径：路径：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简单路径：简单路径

9、：1，2，5，7，6回路：回路：1，2，5，7，6，5，2，1简单回路：简单回路：1，2，3，1若无向图中任意两个顶点之间都有路径相通，则称此图为连通图连通图;若无向图为非连通图，则图中各个极大连通子图称作此图的连通连通分量分量。10. 连通图、连通分量连通图、连通分量BACDFEG1BACDFEG2 若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图强连通图。ABECFABECF对有向图，对有向图， 否则，其各个极大强连通子图称作它的强连通分量强连通分量。11. 强连通图、强连通分量强连通图、强连通分量 假设一个连通图有 n 个顶点和 e 条边，其中 n 个顶点和n-1 条边构成一

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

11、操作对邻接点的操作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. 对邻

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

13、Vex(&G, v); / 删除G中顶点v及其相关的弧。5. 插入或删除插入或删除弧弧InsertArc(&G, v, w); / 在G中增添弧，若G是无向的， /则还增添对称弧。DeleteArc(&G, v, w); /在G中删除弧，若G是无向的， /则还删除对称弧。6. 遍遍 历历DFSTraverse(G, v, Visit(); /从顶点v起深度优先深度优先遍历图G，并对每个顶点调/用函数Visit一次且仅一次。一旦Visit（）失败，/则操作失败。BFSTraverse(G, v, Visit(); /从顶点v起广度优先广度优先遍历图G，并对每个顶点调/用函

14、数Visit一次且仅一次。一旦Visit（）失败，/则操作失败。7.1 图的抽象数据类型定义图的抽象数据类型定义7.2 图的存储表示图的存储表示7.3 图的遍历图的遍历7.4 最小生成树最小生成树7.7 两点之间的最短路径问题两点之间的最短路径问题7.5 拓扑排序拓扑排序7.6 关键路径关键路径7.2 图的存储表示图的存储表示7.2.1 图图的数组的数组()存储表示存储表示7.2.2 图图的的存储表示存储表示7.2.3 有向图有向图的的存储表示存储表示 Aij= 0 , (vi,vj)VR 1 , (vi,vj)VR7.2.1 7.2.1 图的数组(邻接矩阵)存储表示定义定义: nn矩阵的元素

15、为矩阵的元素为0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 2 3 4 5 6123456V1V2V3V4V5V6无向图无向图网的邻接矩阵存储表示定义定义: nn矩阵的元素为矩阵的元素为无向网无向网V1V2V3V4V5V615671122512 1 2 3 4 5 61234568888888888888 888 88888 Aij= wi,j ,(vi,vj) VR ,(vi,vj) VR8有向图的邻接矩阵为有向图的邻接矩阵为非对称矩阵非对称矩阵V1V2V4V3V50 1 0 1 0 0 0

16、 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 1 2 3 4 512345出度？入度？出度？入度？出度出度入入度度 typedef struct / 图的定义图的定义 MGraph;typedef struct ArcCell / 弧的定义弧的定义 VRType adj; / VRType是顶点关系类型。 / 对无权图，用1或0表示相邻否； / 对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; VertexType vexsMAX_VERT

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

18、umStatus CreateUDN (Mgraph &G) /构造无向图 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=LocateV

19、ex(G,v1); j= LocateVex(G,v2); /定位v1, v2 G.arcsij.adj=1; /弧的邻接关系 if(IncInfo) Input (*G.); 输入边相关信息 G.arcsji= G.arcsij; /置邻接矩阵对称值 DBACFE7.2.2 图图的邻接表存储表示的邻接表存储表示顶点顶点:顺序存储顺序存储边边:单链表存储单链表存储 data firstarcadjvex nextarc info A B C D E F 1 4 0 4 53 52 50 11 2 3012345有向图的邻接表有向图的邻接表1 4230 12 A B C D

20、 EABECD 在在有向图的邻接表有向图的邻接表中不易找到指向该顶中不易找到指向该顶点的弧。点的弧。仅记录以该顶点为弧尾的弧.01234ABECD有向图的有向图的邻接表邻接表 在有向图的逆逆邻接表中，对每个顶点，链接的是指向该顶点的弧，即以该顶点为的弧。 A B C D E 303420 012341 图的邻接表存储定义图的邻接表存储定义分三部分：分三部分：DBACFE A B C D E F 1 40 4 53 52 50 11 2 3顶点的结点结构顶点的结点结构弧的结点结构弧的结点结构图的结构定义图的结构定义012345typedef struct AdjList vertices; /顶

21、点向量 int vexnum, arcnum; / 图的当前顶点数和弧数 int kind; / 图的种类标志 ALGraph;图的结构定义图的结构定义(邻接表)typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; data firstarc顶点的结点结构顶点的结点结构typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的

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

23、001100000000100010010001100000000010A1 50 42 31 v1 v2 v3 v4 v5 v6 0123455 2 50 31 35 v1 v2 v3 v4 v5 v6 2 012345将有向图的邻接表将有向图的邻接表和逆邻接表合起来和逆邻接表合起来将有向图的邻接表将有向图的邻接表和逆邻接表合起来和逆邻接表合起来三部分三部分：顶点的结点结构顶点的结点结构弧的结点结构弧的结点结构图的结构定义图的结构定义7.2.3 有向图有向图的十字链表存储表示的十字链表存储表示 ABECD 逆邻接表逆邻接表 A B C D E 3 0 3 4 2 0 01234 4 1 42

24、30 12 A B C D E 邻接表邻接表 01234顶点的结点结构顶点的结点结构顶点信息数据 指向该顶点的第一条入弧第一条入弧指向该顶点的第一条出弧第一条出弧typedef struct VexNode / 顶点的结构表示顶点的结构表示 VertexType data; ArcBox *firstin, *firstout; VexNode;datafirstinfirstout弧的结点结构弧的结点结构弧尾顶点位置 弧头顶点位置 弧的相关信息指向下一个有相同弧尾有相同弧尾的结点指向下一个有相同弧头有相同弧头的结点typedef struct ArcBox / 弧弧的结构表示的结构表示 in

25、t tailvex, headvex; InfoType *info; struct ArcBox *hlink, *tlink; ArcBox ;hlink tlinktailvexheadvexinfotypedef struct VexNode xlistMAX_VERTEX_NUM; / 顶点结点(表头向量) int vexnum, arcnum; /有向图的当前顶点数和弧数 OLGraph;图的结构定义图的结构定义2 33 13 03 22 00 10 2V1V2V3V40123例如：例如： v1v4v2v301231 0若增加一条边若增加一条边练习练习：画画出有向图出有向图G的十字

26、链表。的十字链表。V1V3V5V4V2G2 13 00 1V1V2V3V4V5012341 21 32 33 4出链入链7.3 图的遍历图的遍历树树的遍历：的遍历： 从根开始遍历； 遍历可以从左到右，从上到下； 存储结构不改变遍历结果；深度优先搜索深度优先搜索DFS (Depth_First Search)广度优先搜索广度优先搜索BFS(Breadth_First Search)图的遍历图的遍历: 从图中某一顶点出发遍历图中其余顶点， 使得每个结点均被访问一次均被访问一次，而且仅被访问一次仅被访问一次。 从图中某个顶点V0 出发，访问此顶点，然后依次从依次从V0的各个的各个未被访问的邻接未被访

27、问的邻接点出发点出发深度优先搜索遍历图深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。7.3.1、深度优先搜索、深度优先搜索连通图的深度优先搜索遍历连通图的深度优先搜索遍历1. 访问顶点访问顶点 V ;2. for (W1、W2、W3 ) 若该邻接点若该邻接点Wi未被访问，未被访问， 则深度优先搜索遍历该子图则深度优先搜索遍历该子图。1. 访问根结点；访问根结点；2. 先序遍历左子树；先序遍历左子树；3. 先序遍历右子树。先序遍历右子树。二叉树的先根先根遍历图的深度优先深度优先遍历根根左子树右子树根根子图子图3 3子图子图1 1子图子图2 2Vw1w3w2w1w2w3深度优先

28、搜索举例深度优先搜索举例:BACDFE从从B点开始遍历点开始遍历I. BAEFDC深度优先搜索举例深度优先搜索举例:BACDFE从从B点开始遍历点开始遍历.BEAFCDI. BAEFDC深度优先搜索遍历归纳深度优先搜索遍历归纳:1.深度优先搜索遍历连通图的过程类似于树的先根遍历;3. 解决的办法是:为每个顶点设立一个 “访问标志 visitedw”;2. 遍历过程需要判别V的邻接点是否被访问？void DFS(Graph G, int v) / 从顶点从顶点v出发，出发，深度优先搜索遍历连通图深度优先搜索遍历连通图 G visitedv = TRUE; VisitFunc(v); for(w=

29、FirstAdjVex(G, v); w=0;w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 对v的尚未访问的邻接顶点w / 递归调用DFS / DFS深度优先搜索深度优先搜索遍历算法遍历算法:0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 2 3 4 5 6123456基于基于邻接矩阵邻接矩阵的的深度优先搜索举例深度优先搜索举例从从B点开始遍历点开始遍历 visited 0, 0, 0, 0, 0, 0 邻接矩阵DBACFEB A E F C D

30、顶点向量 A, B, C, D, E, F void DFS_M(MGraph G, int i, int n) / 从顶点Vi出发，深度优先搜索遍历邻接矩阵图 G visitedi = TRUE; /标记Vi已被访问过 couti“ ” ; /输出Vi for(j=0; jn; j+) /依次搜索Vi的每个邻接点 if (G.arcsij!=0&!visitedj ) DFS _M(G, j, n); /若Vi的一个有效邻接点未被访问过， /则递归调用 / DFS _M基于基于邻接表邻接表的的深度优先搜索举例深度优先搜索举例 A B C D E F 1 4 0 4 53 52 50

31、11 2 3从从A点开始遍历点开始遍历 visited 0, 0, 0, 0, 0, 0 A B E F C DDBACFE012345void DFS_AL(ALGraph G, int i, int n) / 从顶点Vi出发，深度优先搜索遍历邻接表表示的图G visitedi = TRUE; /标记Vi已被访问过 coutiadjvex； if (! visitedj ) /若Vj未被访问过，则递归调用 DFS _AL(G, j, n); p=p- nextarc; /使p指向vi单链表的下一个邻接点 /while / DFS _AL基于基于邻接表邻接表的的深度优先搜索算法深度优先搜索算法

32、 首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。非连通图的深度优先搜索遍历非连通图的深度优先搜索遍历F F F F F F F F F0 1 2 3 4 5 6 7 8abchdekfgTT TT T TTTTa c h d kfe b gachkfedbg访问标志访问标志: :访问次序访问次序: :例如例如:812345670 从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问未被访问过的邻接点，之后按这些顶点被访问的按这些顶点被访问的先后次序先后次序依次访问它依次访问它

33、们的邻接点们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。：从起始点V0出发，由近至远，依次访问和V0有路径相通且路径长度为1，2，的顶点。7.3.2 广度优先搜索广度优先搜索 7.3.2 广度优先搜索广度优先搜索Vw1w8w3w7w6w2w5w4 对连通图，从起始点V到其余各顶点必定存在路径。 其中，V-w1, V-w2, V-w8 的路径长度为1;V-w7, V-w3, V-w5 的路径长度为2;V-w6, V-w4 的路径长度为3。w1Vw2w7w6w3w8w5w4类似于树的按层次遍历 遍历顺序：V W1W2W8W7W3W5W6W4广度优先搜索算法分析广度优先搜索算法分析广度优

34、先搜索遍历顺序： V W1W2W8W7W3W5W6W4Vw1w8w3w7w6w2w5w4w1Vw2w7w6w3w8w5w4 广度优先搜索算法广度优先搜索算法void BFSTraverse(Graph G, int v ) 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.

35、4 最小生成树最小生成树7.4.1 连通图的生成连通图的生成树树7.4.2 连通网的最小生成树连通网的最小生成树 对连通图对连通图进行遍历时，从任意一顶点出发，进行进行遍历时，从任意一顶点出发，进行深度和广度优先搜索便可访问所有的顶点深度和广度优先搜索便可访问所有的顶点。通过遍历，。通过遍历，得到连通图的所有顶点集合，同时将连通图的边分成得到连通图的所有顶点集合，同时将连通图的边分成两个子集：遍历过程中连接顶点的边两个子集：遍历过程中连接顶点的边T(G)和剩余的边和剩余的边B(G)。 遍历过程遍历过程中得到的顶点和边构成连通图的中得到的顶点和边构成连通图的生生成树。成树。7.4.1 连通图连通

36、图的生成树的生成树 按照生成树的定义，按照生成树的定义，n 个顶点的连通图的个顶点的连通图的生成树有生成树有 n 个顶点、个顶点、n-1 条边。条边。 一一个连通图可以有多种生成树：个连通图可以有多种生成树： 从从不同的顶点不同的顶点出发得到不同的生成树；出发得到不同的生成树； 采用采用不同的不同的搜索方法搜索方法得到不同的生成树；得到不同的生成树； 采用采用不同的不同的存储结构存储结构得到不同的生成树；得到不同的生成树；p深度优先生成树深度优先生成树 由深度优先搜索得到的生成树；由深度优先搜索得到的生成树；p广度优先生成树广度优先生成树 由广度优先搜索得到的生成树。由广度优先搜索得到的生成树

37、。例7.4.1:画出下面有向图的DFS生成树与BFS生成树。V2V4V5V3V7V6V1V2V4V5V3V7V6V1V2V4V5V3V7V6V1练习练习：画出从顶点v1开始的DFS与BFS生成森林。V2V4V5V3V7V6V1V8V2V4V5V3V7V6V1V8DFS生成森林V2V4V5V3V7V6V1V8BFS生成森林 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如如何在最节省经费的前提下建立何在最节省经费的前提下建立这个通讯网通讯网？问题：7.4.2 连通连通网网的最小代价生成树的最小代价生成树北京济南郑州青岛广州大连7131791812752410

38、l顶点顶点表示城市表示城市l权权值值城市间建立通信线路所需花费代价城市间建立通信线路所需花费代价 希望找到一棵生成树，它的每条边上的权值之和（希望找到一棵生成树，它的每条边上的权值之和（即建立即建立该通信网所需花费的总代价该通信网所需花费的总代价）最小最小-最小最小代价生成代价生成树树。 构造网的一棵最小代价生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和权值之和”最小。算法二：克鲁斯卡尔算法二：克鲁斯卡尔()算法算法该问题等价于：该问题等价于：算法一：普里姆算法一：普里姆()算法算法 构造最小生成树可以有多种算法，其中大多数算法构造最小生成树可以有多种算法，其

39、中大多数算法都是利用了最小生成树的下述性质：都是利用了最小生成树的下述性质： 设设G G(V(V，E)E)是一个连通网，是一个连通网，U U是顶点集是顶点集V V的一个的一个真子集。若真子集。若(u(u，v)v)是是G G中所有的一个端点在中所有的一个端点在U(U(即即uUuU) )里、另一个端点不在里、另一个端点不在U(U(即即vVvV-U)-U)里的边中，具有最里的边中，具有最小权值的一条边，则一定存在小权值的一条边，则一定存在G G的一棵最小生成树包的一棵最小生成树包含此边含此边(u(u，v)v)。这个性质称为。这个性质称为性质。性质。 ( ( inimum inimum ost ost

40、 panning panning ree)ree)设设T T是是G G的一棵最小生成树，但不包含的一棵最小生成树，但不包含边边(u(u，v)v)。由于。由于T T是树，且是连通的，因此必有一条从是树，且是连通的，因此必有一条从u u到到v v的路径；且该路径上必有一条连接两个顶点集的路径；且该路径上必有一条连接两个顶点集U U和和V-UV-U的边的边( u( u，v)v)，其中，其中 u Uu U，v V-Uv V-U，否则，否则u u和和v v不连不连通。当把边通。当把边(u(u，v)v)加入树加入树T T时，得到一个含有边时，得到一个含有边(u(u，v)v)的回的回路，见下页图。删去边路，

41、见下页图。删去边( u( u，v)v)，上述回路即被消除，上述回路即被消除，由此得到另一棵生成树由此得到另一棵生成树TT，TT和和T T的区别仅在于用边的区别仅在于用边(u(u，v)v)取代了取代了T T中的边中的边( u( u，v)v)。因为。因为(u(u，v)v)的权的权( u( u，v)v)的权，故的权，故TT的权的权T T的权，因此的权，因此TT也是也是G G的最小生成树，的最小生成树，它包含边它包含边(u(u，v)v)， abcdegf19141827168213127U= , abV-U= , , , , efdcg首先首先从从V V中任取一个顶点中任取一个顶点u u0 0，将生成

42、树，将生成树T T置为仅有一置为仅有一个结点个结点u u0 0的树，即置的树，即置U Uuu0 0 ；然后只要；然后只要U U是是V V的真子集，的真子集，就在所有那些：一个顶点就在所有那些：一个顶点u u已在已在T(T(即即uUuU) )、另一个顶点、另一个顶点v v还未在还未在T(T(即即vVvV-U)-U)的边中，找一条权值最小的边的边中，找一条权值最小的边(u(u，v)v)，并把该条边，并把该条边(u(u，v)v)并入并入T T的边集、其不在的边集、其不在T T中的顶点中的顶点v v并入顶点集并入顶点集U U中。如此进行下去，每次往生成树里并入中。如此进行下去，每次往生成树里并入一个顶

43、点和一条边，直到把所有顶点都包括进生成树一个顶点和一条边，直到把所有顶点都包括进生成树T T为止。此时，必有为止。此时，必有U UV V，TETE中有中有n-1n-1条边。条边。 v1v2v3vkvnv0原图顶点集合原图顶点集合V-Uv0v196156915720vk7最小生成树顶点集合最小生成树顶点集合U92025ABCDEF101015121287655ABCDEF107610ABCDEF1015125ABCDEF1015765ABCDEF1015765ABCDEF1076105ABCDEF107610abcdegf195141827168213127例如例如: :aedcbgf14853

44、1621所得生成树权值和 = 14+8+3+5+16+21 = 67 假设在生成树的构造过程中，图中 n 个顶点分属两个集合：落在生成树上的顶点集 U 和尚未落在生成树上的顶点集 V-U 。 下一步应该在所有在所有连通连通U中和中和V-U中的顶点的边中，中的顶点的边中，选取权值最小的选取权值最小的边边。V-U U普里姆算法的关键普里姆算法的关键:struct VertexType adjvex; / 顶点 VRType lowcost; / 权值 closedgeMAX_VERTEX_NUM; 设置一个辅助数组，以记录从设置一个辅助数组，以记录从U到到VU具具有最小代价的边。对每个顶点有最小代

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

46、合在集合V-U中中)的那些顶点中选择的那些顶点中选择.lowcost 最小的顶点加入到集合最小的顶点加入到集合U中，同时将相关顶点的中，同时将相关顶点的closedge作相应的调整。作相应的调整。普里姆算法的实现：普里姆算法的实现：abcdegf195141827168213127 closedge a b c d e f g Adjvex Lowcost aedb基于邻接矩阵的基于邻接矩阵的 普里姆算法普里姆算法0 1 2 3 4 5 6ca19aaaaaa141888800gf12e8e16e03d21d7d5c000019141819571253738211412816212718162

47、7a b c d e f gabcdefg 普里姆算法归纳(基于邻接矩阵存储结构)： 1. 根据起始顶点初始化辅助数组；根据起始顶点初始化辅助数组；2. 起始顶点起始顶点lowcost值置值置0 ；3.循环处理其余循环处理其余n-1个顶点；个顶点； 求剩余顶点中求剩余顶点中lowcost值值最小的顶点最小的顶点k; 输出顶点输出顶点k和边作为生成树的一个结点和边；和边作为生成树的一个结点和边； 将第将第k 个顶点的个顶点的lowcost置置0，表示加入，表示加入U集；集； 循环将新顶点并入循环将新顶点并入U集后重新选择最小边；集后重新选择最小边；void MiniSpanTree_P(MGra

48、ph 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) ?继续继续向生成树上添加顶点向生成树上添加顶点;见下页。见下页。 k = minimum(closedge); / 求出加入生成树的下

49、一个顶点求出加入生成树的下一个顶点(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 ; 考虑问题的出发点考虑问题的出发点: 为使生成树上，则应使生成树中每一条边的权值尽可

50、能地小。 假设假设图图G（V，VR）是一个连通图；）是一个连通图； 先构造一个只含 n 个顶点且无边的非连通图T（V， ），图中每个顶点自成一个连通分量； 从图G中选择权值最小的边，如果该边的两个顶点落在图T的上，则将该边加入到T中，否则选择下一条边； 如此重复，直至加上 n-1 条边为止。例例: :5148213aedcbgfabcdegf19514627168213ae12dcbgf76初始值为某个顶点初始值为某个顶点(即即1个连通个连通分量分量)，在，在一个连通分量上添加边和顶点。一个连通分量上添加边和顶点。 初始值为初始值为n个顶点个顶点(即即n个连通个连通分量分量)，每次，每次使连通

51、分量的个数减一。使连通分量的个数减一。 用一句话描述两种算法练习练习：利用Prim算法、Kruskal算法构造最小生成树。gde afcbh21112221234gde afcbh2111221结果：7.1 图的抽象数据类型定义图的抽象数据类型定义7.2 图的存储表示图的存储表示7.3 图的遍历图的遍历7.4 最小生成树最小生成树7.7 两点之间的最短路径问题两点之间的最短路径问题7.5 拓扑排序拓扑排序7.6 关键路径关键路径7.5 拓扑排序拓扑排序132546问题引入：问题引入：某一某一项工程的流程图项工程的流程图对于此工程，我们关心的两个问题是：对于此工程，我们关心的两个问题是：（1）工

52、程是否能顺利进行（判定有向图是否有环）。）工程是否能顺利进行（判定有向图是否有环）。（2）估算整个工程完成所必须的最短时间。）估算整个工程完成所必须的最短时间。对应于有向图，即为以下两个问题：对应于有向图，即为以下两个问题：（1）对有向图进行拓朴排序。）对有向图进行拓朴排序。（2）求有向无环图的关键路径。）求有向无环图的关键路径。7.5.1 什么是什么是“拓扑排序拓扑排序”？ 对有向图（AOV网(Activity On Vertex)顶点表示活动, 弧表示优先关系）进行如下操作: 按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序

53、关系。 由此所得顶点的线性序列称之为拓扑有序序列。 例：对于下列有向图BDAC可求得拓扑有序序列： A B C D 或 A C B D7.5 拓扑排序拓扑排序1127.5 拓扑排序拓扑排序学生课程学习工程图学生课程学习工程图BDAC对于下列有向图不能求得它的拓扑有序序列。不能求得它的拓扑有序序列。因为图中存在一个回路 B, C, D如果有向图存在环，则不能够进行如果有向图存在环，则不能够进行拓扑排序；反之，如果对一个有向图不能够进拓扑排序；反之，如果对一个有向图不能够进行拓扑排序，则一定存在环。行拓扑排序，则一定存在环。因此因此，通过拓扑排序可以判断一个有向图是否存在环。，通过拓扑排序可以判断

54、一个有向图是否存在环。7.5.2 如何如何进行拓扑排序？进行拓扑排序？1、从有向图中选取一个没有前驱没有前驱的顶点， 并输出之; 3、重复上述两步，可能得到两种结果： (1) 图空拓扑排序成功拓扑排序成功! (2) 图不空,但找不到无前驱的顶点有环有环!2、从有向图中删去此顶点以及所有以它删去此顶点以及所有以它 为尾的弧为尾的弧;abcghdfeabhc dgfe 没有前驱的顶点没有前驱的顶点删除顶点及以它为尾的弧删除顶点及以它为尾的弧 = 弧头顶点的入度减弧头顶点的入度减1abcghdfe需要设一个数组inDegreew，记录顶点的入度数 = 入度为零的顶点入度为零的顶点初始化 inDegr

55、eew；while(取一个新的入度为零的顶点v) printf(v); +m; /对输出顶点计数 for( w=FirstAdj(v); w; w=nextAdj(v,w) inDegreew-; if (mn) printf(“图中有回路”);拓扑排序拓扑排序算法描述算法描述: 为避免每次都要搜索入度为零的顶点，在算法中设置一个“栈栈”，以保存“入度为零”的顶点。Status TopologicalSort( ALGraph G) FindInDegree(G,indegree); /计算各顶点的入度 InitStack(S); count=0; for ( i=0; iG.vexnum;

56、+i) if (!indegreei) Push(S, i); /入度为零的顶点入栈 while (!EmptyStack(S) Pop(S, v); +count; printf(v); for (w=FirstAdj(v); w; w=NextAdj(G,v,w) -indegreew; / 弧头顶点的入度减1 if (!indegreew) Push(S, w); / 入度为零顶点入栈 /whileif (countG.vexnum) printf(“图中有回路”)7.1 图的抽象数据类型定义图的抽象数据类型定义7.2 图的存储表示图的存储表示7.3 图的遍历图的遍历7.4 最小生成树最

57、小生成树7.7 两点之间的最短路径问题两点之间的最短路径问题7.5 拓扑排序拓扑排序7.6 关键路径关键路径7.6 关键路径关键路径 (拓扑排序) (关键路径)例如：例如：假设以有向网表示一个施工图，弧上的权值表示完成假设以有向网表示一个施工图，弧上的权值表示完成该项子工程所需时间。该项子工程所需时间。abcdefghp64521187244研发研发开始开始组件组件1图纸图纸组件组件2图纸图纸组件组件3图纸图纸工艺工艺图纸图纸订购订购合同合同部件部件1入库入库部件部件2入库入库新产品新产品完成完成AOE网网(Activity On Edge) 边表示活动边表示活动 , 顶点表示事件，顶点表示事

58、件，权表示活动持续时间权表示活动持续时间7.6 关键路径关键路径整个工程的完成时间？整个工程的完成时间？哪些子工程将影响整个工程的完成时间？哪些子工程将影响整个工程的完成时间？abcdefghp64521187244研发研发开始开始组件组件1图纸图纸组件组件2图纸图纸组件组件3图纸图纸工艺工艺图纸图纸订购订购合同合同部件部件1入库入库部件部件2入库入库新产品新产品完成完成整个工程完成的时间：从有向图的源点源点到汇点汇点的最长路径。abcdefghp64521187244“关键活动”：该弧上的权值增加权值增加 将使有向图上的最长路径的长度增加。最长路径的长度增加。源点汇点6174构成最长路径的所

59、有活动均为构成最长路径的所有活动均为“关键活动关键活动” 。 如何求关键活动？如何求关键活动？“事件(顶点)” 的 最早发生时间 ve(j)“事件(顶点)” 的 最迟发生时间 vl(k)“活动(弧)” 的 最早开始时间 e(j)“活动(弧)” 的 最迟开始时间 l(k)完成第i项活动的时间余量: l(i)- e(i) “关键活动关键活动”必为必为:l(i)-e(i) = 0,即即 e(i) = l(i) 的活动。的活动。分析分析:如何如何找找e(i)=l(i)的关键活动？的关键活动？设活动设活动ai用弧用弧表示，其持续时间记为：表示，其持续时间记为：dut()则有：（则有：（1）e(i)=ve

60、(j) （2）l(i)=vl(k)-dut()如何求如何求ve(j)和和vl(j)？(1)从从ve(1)=0开始向前递推开始向前递推为弧头的弧的集合是所有以其中jTnjTjijidutiveMaxjvei2 ,),()()(2)从从vl(n)=ve(n)开始向后递推开始向后递推为弧尾的弧的集合是所有以其中iSniSjijidutjvlMinivlj11 ,),()()(jkaijiq求关键路径步骤n求ve(i)n求vl(j)n求 e(i)n求 l(i)n计算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点 ve vl0645771614180668710161418a1a2a3a4a5a6a7a8