新版数据结构第7章图3ppt

1、第七章(Zhang) 图7.1 图的(De)类型定义7.2 图的存储结构7.3 图的遍历7.4 最小生成树7.5 有向无环图及其应用7.6 最短路径第一页，共六十一页。7.3 图(Tu)的遍历图的遍历：从图中某个顶点出发游历图，访遍图中其余(Yu)顶点，并且使图中的每个顶点仅被访问一次的过程。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组 visit0.n-1 作为对顶点的标记，当顶点vi未被访问，visiti 值为0；当vi已被访问，则 visiti 值为1。通常，有两种遍历图的路径：深度优先搜索和广度优先搜

2、索，对无向图和有向图都适用。第二页，共六十一页。图的两种遍历方法：1.深度优先搜索图的深度优先遍历类似于树的先根遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就称之为图的深度优先遍历。2.广度优先搜索广度优先遍历类似于树的按层(Ceng)次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历就称为广度优先遍历。第三页，共六十一页。1. 深(Shen)度优先搜索 DFS基本思想：选择图中某个(强)连通分量中某个顶点v出发：

3、访问顶点 v，并将其访问标记置为访问过，即 visitedv = 1；依次从 v 的未被访问的邻接点出发，继续对图进行深度优先遍历，直到 (强)连通分量中和v有路径相通的顶点都被访问过；如果图中还有顶点未被访问，则另选图中其余(强)连通分量中一个未被访问的顶点作起点，重复(Fu)上述过程，直至图中所有顶点都被访问过为止。第四页，共六十一页。非连通图的每一个连通部分称为连通分量。连通分量：连通：在无向图中，如果从顶点v到顶点w有路径，则称v和w是连通的。LABMCFIDGJEHKDEIGHKLABMCFJ第五页，共六十一页。(强)连通分量的遍历：W1、W2 和(He) W3 均为 V 的邻接点。

4、SG1 为从 W1 出发可以访问到的顶点集；SG2 为从 W2 出发可(Ke)以访问到的顶点集；SG3 为从 W3 出发可以访问到的顶点集。访问顺序：SG1 SG2 SG3。交集部分只访问一次。第六页，共六十一页。第七页，共六十一页。abchdekfg812345670F F F F F F F F F0 1 2 3 4 5 6 7 8TTTTTTTTTachdkfe bgachkfedbg访问标(Biao)志:访问(Wen)次序:例如:hk第八页，共六十一页。void DFSTraverse (Graph G ) / 深度优先遍历 for (v = 1; v = G.vexnum; +v)

5、visitedv = FALSE; / 访问标志数组(Zu)初始化 for (v = 1; v =0; w = NextAdjVex(G, v, w) if(!visitedw) DFS(G, w, Visit); / DFS深度优先遍历的递归算法第九页，共六十一页。例1：深度优(You)先遍历图G，并写出深度优先遍历序列。序列1： V1,V2,V4,V8,V5,V3,V6,V7序列2： V1,V2,V5,V8,V4,V3,V7,V6V1V2V4V5V3V7V6V8注意：由于没有规定访问邻接点的顺序，深度优先序列不(Bu)是唯一的。第十页，共六十一页。例2：深(Shen)度优先遍历图G，并写出

6、深度优先遍历序列。V1V2V4V5V3V7V6V8深度优先(Xian)遍历序列：V1, V2, V4, V8, V5, V6, V3, V7V1, V2, V5, V8, V4, V6, V3, V7V1, V3, V7 , V8, V6, V5, V2, V4 第十一页，共六十一页。深度优先遍历序列 对图进行深度优先遍历时，按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列，或DFS序列。一个图的DFS序列不一定惟一;源点和存储结构的内容均已确定的图的DFS序列惟一。 邻接矩阵表示的图确定源点后，DFS序列惟一；只有给(Gei)出了邻接表的内容及初始出发点，才能惟一确定其DFS序列

7、第十二页，共六十一页。例3：已知图的(De)邻接表如下，求从顶点0出发的深度优先遍历序列。深度(Du)优先遍历序列： 0, 1, 2, 3, 4132120413204V0V1V2V3V401234 V0 V4 V3 V1 V2深度优先遍历序列：0, 1, 2, 3, 40, 1, 2, 4, 30, 1, 4, 2, 30, 3, 2, 1, 40, 3, 2, 4, 1第十三页，共六十一页。例4：已知图的邻接矩阵，求从顶点0出发的深度(Du)优先遍历序列。深度优先遍(Bian)历序列： 0, 1, 3, 4, 2, 5, 6第十四页，共六十一页。例5：已知图的邻接表如下，求(Qiu)从顶点

8、0出发的深度优先遍历序列。深(Shen)度优先遍历序列： 0, 1, 2, 3第十五页，共六十一页。2.广度优(You)先搜索 BFS选择(强)连通分量中的某个顶点vi出发：访问顶点vi，并将其访问标志置为已被访问，即visitedvi=1；访问 vi 的所有未(Wei)被访问的邻接点w1, w2, , wk ；依次从这些邻接点出发，访问它们的所有未被访问的邻接点，直到(强)连通分量的所有顶点都被访问； 重复上述步骤，直到图中所有的顶点都被访问。第十六页，共六十一页。对连通图，从起点V到(Dao)其余各顶点必定存在路径。 其中(Zhong)，Vw1, Vw2, Vw5的路径长度为1；Vw3,

9、Vw6, Vw8 的路径长度为2；Vw4, Vw7 的路径长度为3各顶点和起点之间存在“远近”关系。就是按照“由近到远”的顺序进行遍历。第十七页，共六十一页。void BFSTraverse (Graph G, Status (*Visit)(int v)/ 广度优先非递归遍历。使用辅助队列Q和访问标志数(Shu)组visited。 for (v = 1; v G.vexnum; +v) visitedv = FALSE; InitQueue(Q); / 置空的辅助队列Q for (v = 1; v =0; w=NextAdjVex(G, u, w) / 访问(Wen)邻接点 if ( !vi

10、sitedw) / u的尚未访问的邻接顶点w入队列Q visitedw = TRUE; (*Visit)(w); EnQueue(Q, w); / if / while / BFSTraverse第十九页，共六十一页。例1：广度优(You)先遍历图G，并写出广度优先遍历序列。 广度优先遍历序列： V1,V2,V3,V4,V5,V6,V7,V8V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8例2：广度优先遍历(Li)图G，并写出广度优先遍历序列。广度优先遍历序列：V1,V2,V3,V4,V5,V6,V7,V8第二十页，共六十一页。图的广度优先遍历序列 广度优先遍历图所得的顶点序列

11、，定义为图的广度优先遍历序列，简称BFS序列。一个(Ge)图的BFS序列不一定是惟一的;给定了源点及图的存储结构时，BFS序列就是惟一的。第二十一页，共六十一页。例3：已知图的邻接表如下，求(Qiu)从顶点0出发的广度优先遍历序列。广度优先遍(Bian)历序列： 0, 1, 3, 2, 4132120413204V0V1V2V3V401234 V0 V4 V3 V1 V2广度优先遍历序列：0, 1, 3, 2, 40, 1, 3, 4, 20, 3, 1, 2, 4第二十二页，共六十一页。例4：已知图(Tu)的邻接矩阵，求从顶点0出发的广度优先遍历序列。0, 1, 2, 3, 4, 6, 5广

12、度优先遍(Bian)历序列：第二十三页，共六十一页。例5：已知图的邻接表如下，求从顶点0出发的广度优先遍(Bian)历序列。0, 3, 2, 1广度优先遍历序列：0, 3, 2, 1深度优先遍历序列：第二十四页，共六十一页。例6：画出该网的邻接矩阵。根据画出的邻接矩阵存储结构，从顶点(Dian)1出发，分别进行深度优先遍历和广度优先遍历；第二十五页，共六十一页。201521030410154101 2 3 4 5 61 2 3 4 5 6 深(Shen)度优先：1，2，5，4，6，3广度优先：1，2，3，5，6，4第二十六页，共六十一页。非连通图的每一个连通部分称为连通分量。连通分量：连通分量

13、：无向图中的极大连通子图。极大连通子图：该子图是无向图D的连通子图，将D的任(Ren)何不在该子图中的顶点加入，子图不再是连通的；生成树：包含无向图G中所有n个顶点和n-1条边的极小连通子图称为G的生成树。极小(Xiao)连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。若T是G的生成树当且仅当T满足如下条件：1. T是G的连通子图 2. T包含G的所有顶点3. T中无回路7.4 最小生成树第二十七页，共六十一页。7.4 最小生成(Cheng)树假设要在 n 个城市之间建立通讯联络网，如何在最节省经费(Fei)的前提下建立这个通讯网？问 题：分析：首先，该网必须是连通网；

14、 其次，网中的线路必须最少； 最后，考虑所有线路的长度之和最小。最小生成树满足上述要求。第二十八页，共六十一页。上述问题等价于：构造网的一棵最小生成树，即：在 e 条带权(Quan)的边中选取 n-1 条边（不构成回路），使“权值之和” 最小。求最小生成树的两个算法：普里姆算法：适用于求边稠密的网的最小生成树。克鲁斯卡尔算法：适用于求边稀疏的网的最小生成树。第二十九页，共六十一页。假(Jia)设有连通网 N = V, E ，求 N 的最小生成树 T = TV, TE 。算法的(De)基本思想:一、普里姆(Prim)算法令 TV = v , TE = ；/从一个顶点v开始TE += min(v,

15、 u)，TV += u，其中, vTV, uV-TV;重复步骤 2，直到 TV = V。第三十页，共六十一页。 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含(Han)有 n 个顶点为止。普里姆算法的基(Ji)本思想:第三十一页，共六十一页。V2V0V3V5V4骤： (1)初始时， U=v0，边(Bian)集合TE= ； (2)在所有 v0U 、wV-U的边中选择一条权值最小的

16、边，设这条边为（v0, w）； (3)将边 (v0,w) 加入TE，同时将w 加入U中，而把w从V-U中删掉； (4)重复(2)、(3)，直到U=V为止。第三十二页，共六十一页。V3V1V4V6V5V23652165546(1)普里姆算(Suan)法举例 例1 使用(Yong)普里姆算法为图G构造最小生成树。 设最小生成树为： T( U， TE )图 G( V, E ) 构造步骤如下：第三十三页，共六十一页。步骤(Zhou) 1 ：初始状态 Uv1 TE= V-U=v2,v3,v4,v5,v6V1(1)普里姆算法举(Ju)例V3V1V4V6V5V23652165546图 G( V, E ) 第

17、三十四页，共六十一页。步(Bu)骤 2 ：V3V11 Uv1,v3 V-U= v2,v4,v5,v6(1)普里姆算法(Fa)举例V3V1V4V6V5V23652165546图 G( V, E ) 第三十五页，共六十一页。步(Bu)骤 3 ：V3V1V614 Uv1, v3, v6 V-U= v2,v4,v5(1)普里姆算法(Fa)举例V3V1V4V6V5V23652165546图 G( V, E ) 第三十六页，共六十一页。步(Bu)骤 4 ： Uv1, v3, v6,v4 V-U= v2,v5V3V1V4V6142(1)普里姆算(Suan)法举例V3V1V4V6V5V23652165546图

18、 G( V, E ) 第三十七页，共六十一页。步(Bu)骤 5 ： Uv1, v3, v6,v4,v2 V-U= v5V3V1V4V6V21425(1)普里姆算法(Fa)举例V3V1V4V6V5V23652165546图 G( V, E ) 第三十八页，共六十一页。步(Bu)骤 6 ： Uv1,v2,v3,v4,v5,v6 UV，结(Jie)束V3V1V4V6V5V214253(1)普里姆算法举例V3V1V4V6V5V23652165546图 G( V, E ) 第三十九页，共六十一页。在算法实现中设(She)置一个辅助数组 closedege，对当前 V-U 集合中的每个顶点，记录和顶点集

19、U 中顶点相连接的代价最小的边；struct VertexType adjvex; / U集中的相(Xiang)邻顶点序号 VRType lowcost; / 边的权值 closedgeMAX_VERTEX_NUM;第四十页，共六十一页。例(Li)如:所得生成树权(Quan)值和 = 14+8+3+5+16+21 = 67第四十一页，共六十一页。abcdegf195141827168213127aedcbaaa19141814例(Li)如:e12ee8168d3dd7213c55所得生成树权值(Zhi)和= 14+8+3+5+16+21 = 67第四十二页，共六十一页。abcdegf19514

20、1827168213127例(Li)2:aedcbgf148531621所得生成树权值(Zhi)和= 14+8+3+5+16+21 = 67第四十三页，共六十一页。void MiniSpanTree_P (MGraph G, VertexType u) / 用 Prim 算法从顶点 u 出发构造网 G 的最小生成树(Shu) / 网 G 用邻接矩阵表示 k = LocateVex( G, u );max = 100; for ( j = 0; j G.vexnum; +j ) / 辅助数组初始化 if ( j != k ) closedgej = u, G.arcskj.adj ; close

21、dgek.lowcost = 0; / 初始，TV = u for ( i = 1; i G.vexnum; +i ) for ( n = 1; n G.vexnum; +i ) if ( closedgen.lowcast max & closedgen.lowcast ) k = n; max = closedgen.lowcast;下(Xia)页第四十四页，共六十一页。 printf ( “(%c, %c)”, closedgek.adjvex, G.vexsk ); / 输出最小(Xiao)生成树的一条边 closedgek.lowcost = 0; / k 顶点并入 TV 集 for

22、 ( j = 0; j G.vexnum; +j ) / 修改顶点的 lowcast if (G.arcskj.adj closedgej.lowcost) closedgej = G.vexsk, G.arcskj.adj ; / for / MiniSpanTree_P第四十五页，共六十一页。练习题1 使用普里姆算法为图(Tu)G构造一棵最小生成树。4 17652653605040705030524542图 G4 176523504050304542最小生成树第四十六页，共六十一页。练习题2 使用普里姆算法为图G构(Gou)造一棵最小生成树。第四十七页，共六十一页。算法(Fa)的基本思想：

23、二(Er)、克鲁斯卡尔(Kruskal)算法假设有连通网 N = V, E ，求 N 的最小生成树 T = TV, TE 。令 TV = V, TE = ； /包含所有顶点TE += min(v, u) , (v, u) 是顶点 v, u 之间的唯一路径;重复步骤 2，直到 TE 中边的条数为 n-1。第四十八页，共六十一页。算法的基(Ji)本思想：考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能(Neng)地小。具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复

24、，直至加上 n-1 条边为止。第四十九页，共六十一页。步骤：(1)最小生成树的初始状(Zhuang)态为只有n个顶点而无边的非连通图 T= (V,)。(2)在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中； 否则，舍去此边，选取下一条代价最小的边。(3)依此类推，直至T中所有顶点都在同一连通分量上为止。第五十页，共六十一页。例2 用克鲁斯卡尔算法构造图G最的小(Xiao)生成树。(2)克鲁斯卡(Ka)尔算法V3V1V4V6V5V23652165546图 G= (V, E) 设最小生成树为： T( U， TE ) 构造步骤如下：第五十一页，共六十一页。V3V1V4V6V5V2步骤1：初(Chu)始状态T中只(Zhi)有 n 个顶点，无边(2)克鲁斯卡尔算法V3V1V4V6V5V23652165546图 G= (V, E) 第五十二页，共六十一页。V3V1V4V6V5V23652165546图(Tu) G= (V, E) 步(Bu)骤2：T中有 n 个顶点，1条边V3V1V4V6V5V21(2)克鲁斯卡尔算法第五十三页，共六十一页。图(Tu) G= (V, E) 步(Bu)骤3：T中有 n 个顶点，2条边V3V1V4V6V5V212(2)克鲁斯卡尔算法V3V1V4V6V5V23652165546第五十四页，共六十一页。图(Tu) G= (V,