数据结构第7章图3

1、7.1 图的类型定义图的类型定义7.2 图的存储结构图的存储结构7.3 图的遍历图的遍历7.4 最小生成树最小生成树7.5 有向无环图及其应用有向无环图及其应用7.6 最短路径最短路径7.3 图的遍历图的遍历图的遍历：从图中：从图中某个顶点出发某个顶点出发游历图，访遍图中其游历图，访遍图中其余顶点，并且使图中的每个顶点余顶点，并且使图中的每个顶点仅被访问一次仅被访问一次的过程。的过程。在图中，访问部分顶点后，可能又沿着其他边回到已在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，被访问过的顶点。为保证每一个顶点只被访问一次，必必须对顶点进行标记须对顶点

2、进行标记，一般用一个，一般用一个辅助数组辅助数组 visit0.n-1 作作为对顶点的标记，为对顶点的标记，当顶点当顶点vi未被访问未被访问，visiti 值为值为0；当；当vi已被访问，则已被访问，则 visiti 值为值为1。通常，有两种遍历图的路径：通常，有两种遍历图的路径：深度优先搜索深度优先搜索和和广度优广度优先搜索先搜索，对，对无向图和有向图都适用无向图和有向图都适用。图的两种遍历方法：图的两种遍历方法：1.1.深度优先搜索深度优先搜索u图的深度优先遍历图的深度优先遍历类似于类似于树的先根遍历树的先根遍历。u采用的搜索方法的特点是尽可能采用的搜索方法的特点是尽可能先对纵深方向先对纵

3、深方向进进行搜索。这种搜索方法称为深度优先搜索行搜索。这种搜索方法称为深度优先搜索(depth-first search)。相应地，用此方法遍历图就称之为。相应地，用此方法遍历图就称之为图的深度优先遍历。图的深度优先遍历。2.2.广度优先搜索广度优先搜索u广度优先遍历广度优先遍历类似于树的类似于树的按层次遍历按层次遍历。u采用的搜索方法的特点是尽可能采用的搜索方法的特点是尽可能先对横向先对横向进行搜进行搜索，故称其为广度优先搜索索，故称其为广度优先搜索(breadth-firstsearch)。相应的遍历就称为广度优先遍历。相应的遍历就称为广度优先遍历。1. 深度优先搜索深度优先搜索 dfs基

4、本思想：基本思想：选择图中某个选择图中某个(强强)连通分量连通分量中某个顶点中某个顶点v出发：出发：访问顶点访问顶点 v，并将其访问标记置为，并将其访问标记置为访问过访问过，即，即 visitedv = 1；依次从依次从 v 的未被访问的的未被访问的邻接点出发邻接点出发，继续对图进行，继续对图进行深度优先遍历，直到深度优先遍历，直到 (强强)连通分量中连通分量中和和v有路径相通有路径相通的顶点都被访问过；的顶点都被访问过；如果图中还有顶点未被访问，则如果图中还有顶点未被访问，则另选另选图中其余图中其余(强强)连通分量连通分量中一个中一个未被访问未被访问的顶点的顶点作起点作起点，重复上述，重复上

5、述过程，直至图中所有顶点都被访问过为止。过程，直至图中所有顶点都被访问过为止。非连通图的每一个非连通图的每一个连通部分连通部分称为称为连通分量连通分量。连通分量：连通分量：连通：连通：在在无向图无向图中，如果从中，如果从顶点顶点v到顶点到顶点w有路径有路径，则，则称称v和和w是连通的。是连通的。labmcfidgjehkdeighklabmcfj(强强)连通分量的遍历：连通分量的遍历：w1、w2 和和 w3 均为均为 v 的的邻接点。邻接点。sg1 为从为从 w1 出发可以访问出发可以访问到的到的顶点集顶点集；sg2 为从为从 w2 出发可以访问到的出发可以访问到的顶点集顶点集；sg3 为从为

6、从 w3 出发可以访问到的出发可以访问到的顶点集顶点集。访问顺序：访问顺序：sg1 sg2 sg3。交集部分交集部分只访问一次。只访问一次。abchdekfg812345670f f f f f f f f f0 1 2 3 4 5 6 7 8t t t t t t t t tach d kfe bgachkfedbg访问标志访问标志: :访问次序访问次序: :例如例如:hkvoid dfstraverse (graph g ) / 深度优先遍历深度优先遍历 for (v = 1; v = g.vexnum; +v) visitedv = false; / 访问标志数组初始化访问标志数组初始化

7、 for (v = 1; v =0; w = nextadjvex(g, v, w) if(!visitedw) dfs(g, w, visit); / dfs深度优先遍历的递归算法深度优先遍历的递归算法 例例1 1：深度优先遍历图：深度优先遍历图g g，并写，并写出深度优先遍历序列。出深度优先遍历序列。序列序列1： v1,v2,v4,v8,v5,v3,v6,v7序列序列2： v1,v2,v5,v8,v4,v3,v7,v6v1v2v4v5v3v7v6v8注意注意：由于没有规定访问邻接点的顺序，：由于没有规定访问邻接点的顺序，深度深度优先序列不是唯一的。优先序列不是唯一的。例例2 2：深度优先遍

8、历图：深度优先遍历图g g，并写出，并写出深度优先遍历序列。深度优先遍历序列。v1v2v4v5v3v7v6v8深度优先遍历序列：深度优先遍历序列：v1, v2, v4, v8, v5, v6, v3, v7v1, v2, v5, v8, v4, v6, v3, v7v1, v3, v7 , v8, v6, v5, v2, v4 深度优先遍历序列深度优先遍历序列 对图进行对图进行深度优先遍历深度优先遍历时，按访问时，按访问顶点的先后次序顶点的先后次序得到的顶点序列称为该图的得到的顶点序列称为该图的深度优先遍历序列深度优先遍历序列，或，或dfs序列。序列。一个图的一个图的dfs序列不一定惟一序列不

9、一定惟一;源点源点和和存储结构的内容存储结构的内容均已均已确定确定的图的的图的dfs序列序列惟一。惟一。u 邻接矩阵邻接矩阵表示的图表示的图确定源点确定源点后，后，dfs序列惟序列惟一；一；u只有给出了只有给出了邻接表邻接表的的内容内容及及初始出发点初始出发点，才，才能能惟一确定其惟一确定其dfs序列序列例例3 3：已知图的邻接表如下，求从顶点：已知图的邻接表如下，求从顶点0 0出发的深度优出发的深度优先遍历序列。先遍历序列。深度优先遍历序列：深度优先遍历序列： 0, 1, 2, 3, 41 13 32 21 12 20 04 41 13 32 20 04 4v0v1v2v3v401234 v

10、0v0 v4v4 v3v3 v1v1 v2v2深度优先遍历序列：深度优先遍历序列：0, 1, 2, 3, 40, 1, 2, 4, 30, 1, 4, 2, 30, 3, 2, 1, 40, 3, 2, 4, 1例例4 4：已知图的邻接矩阵，求：已知图的邻接矩阵，求从顶点从顶点0 0出发的出发的深度优先遍历深度优先遍历序列。序列。深度优先遍历序列：深度优先遍历序列： 0, 1, 3, 4, 2, 5, 60100011101100001011010110011001000110010011011110例例5 5：已知图的邻接表如下，求从顶点：已知图的邻接表如下，求从顶点0 0出发的深度优出发的

11、深度优先遍历序列。先遍历序列。深度优先遍历序列：深度优先遍历序列： 0, 1, 2, 32.广度优先搜索广度优先搜索 bfs选择选择( (强强) )连通分量中的某个顶点连通分量中的某个顶点vi出发：出发：访问顶点访问顶点vi，并将其访问标志置为已被访问，即，并将其访问标志置为已被访问，即visitedvi=1；访问访问 vi 的所有的所有未被访问的邻接点未被访问的邻接点w1, w2, , wk ；依次从这些邻接点出发，访问它们的依次从这些邻接点出发，访问它们的所有未被访问所有未被访问的邻接点的邻接点，直到，直到(强强)连通分量的所有顶点都被访问；连通分量的所有顶点都被访问； 重复上述步骤，直到

12、图中重复上述步骤，直到图中所有的顶点都被访问。所有的顶点都被访问。对连通图，从起点对连通图，从起点v到其余各顶点必定存在路径。到其余各顶点必定存在路径。 其中，其中，vw1, vw2, vw5的路径长度为的路径长度为1；vw3, vw6, vw8 的路径的路径长度为长度为2；vw4, vw7 的路径长度为的路径长度为3各顶点和起点之间存在各顶点和起点之间存在“远近远近”关系。关系。就是按照就是按照“由近到远由近到远”的顺序的顺序进行遍历。进行遍历。void bfstraverse (graph g, status (*visit)(int v)/ 广度优先非递归遍历。使用辅助队列广度优先非递归

13、遍历。使用辅助队列q和访问标志数组和访问标志数组visited。 for (v = 1; v g.vexnum; +v) visitedv = false; initqueue(q); / 置空的辅助队列置空的辅助队列q for (v = 1; v =0; w=nextadjvex(g, u, w) / 访问邻接点访问邻接点 if ( !visitedw) / u的尚未访问的邻接顶点的尚未访问的邻接顶点w入队列入队列q visitedw = true; (*visit)(w); enqueue(q, w); / if / while / bfstraverse例例1 1：广度优先遍历图：广度优

14、先遍历图g g，并写，并写出广度优先遍历序列。出广度优先遍历序列。 广度优先遍历序列：广度优先遍历序列： v1,v2,v3,v4,v5,v6,v7,v8v1v2v4v5v3v7v6v8v1v2v4v5v3v7v6v8例例2 2：广度优先遍历图：广度优先遍历图g g，并写，并写出广度优先遍历序列。出广度优先遍历序列。广度优先遍历序列：广度优先遍历序列：v1,v2,v3,v4,v5,v6,v7,v8图的广度优先遍历序列图的广度优先遍历序列 广度优先遍历图所得的广度优先遍历图所得的顶点序列顶点序列，定义为图的，定义为图的广广度优先遍历序列度优先遍历序列，简称，简称bfs序列。序列。|一个图的一个图的

15、bfs序列不一定是惟一的序列不一定是惟一的;|给定了给定了源点源点及及图的存储结构图的存储结构时，时，bfs序列就是序列就是惟一惟一的。的。例例3：已知图的邻接表如下，求从顶点：已知图的邻接表如下，求从顶点0出发的出发的广度优广度优先先遍历序列。遍历序列。广度优先遍历序列：广度优先遍历序列： 0, 1, 3, 2, 41 13 32 21 12 20 04 41 13 32 20 04 4v0v1v2v3v401234 v0v0 v4v4 v3v3 v1v1 v2v2广度优先遍历序列：广度优先遍历序列：0, 1, 3, 2, 40, 1, 3, 4, 20, 3, 1, 2, 4例例4 4：已

16、知图的邻接矩阵，求：已知图的邻接矩阵，求从顶点从顶点0 0出发的出发的广度优先遍历广度优先遍历序列。序列。0, 1, 2, 3, 4, 6, 50100011101100001011010110011001000110010011011110广度优先遍历序列：广度优先遍历序列：例例5 5：已知图的邻接表如下，求从顶点：已知图的邻接表如下，求从顶点0 0出发的广度优出发的广度优先遍历序列。先遍历序列。0, 3, 2, 1广度优先遍历序列：广度优先遍历序列：0, 3, 2, 1深度优先遍历序列：深度优先遍历序列：例例6：画出该网的邻接矩阵。画出该网的邻接矩阵。根据画出的邻接矩阵存储结构，从顶点根据

17、画出的邻接矩阵存储结构，从顶点1出发，分别出发，分别进行深度优先遍历和广度优先遍历；进行深度优先遍历和广度优先遍历；201521030410154101 2 3 4 5 61 2 3 4 5 6 深度优先：深度优先：1，2，5，4，6，3广度优先：广度优先：1，2，3，5，6，4非连通图的每一个非连通图的每一个连通部分连通部分称为称为连通分量连通分量。连通分量：连通分量：连通分量：连通分量： 无向图中的无向图中的极大连通子图极大连通子图。极大连通子图极大连通子图：该子图是无向图：该子图是无向图d的的连通子图连通子图，将，将d的的任何不在该子图中的任何不在该子图中的顶点顶点加入加入，子图不再是连

18、通的；，子图不再是连通的；生成树：生成树： 包含包含无向图无向图g中所有中所有n个顶点个顶点和和n-1条边条边的的极小极小连通子图连通子图称为称为g的生成树的生成树。极小连通子图极小连通子图：该子图是该子图是g的连通子图，在该子图中删的连通子图，在该子图中删除任何一条除任何一条边边，子图不再连通。，子图不再连通。若若t是是g的的生成树生成树当且仅当当且仅当t满足如下条件：满足如下条件：1. t是是g的的连通子图连通子图 2. t包含包含g的的所有顶点所有顶点3. t中中无回路无回路7.4 最小生成树最小生成树7.4 最小生成树假设要在假设要在 n 个城市之间建立通讯联络网，如何在个城市之间建立

19、通讯联络网，如何在最节省最节省经费的前提下经费的前提下建立这个通讯网？建立这个通讯网？问问 题：题：分析：首先，该网必须是分析：首先，该网必须是连通网连通网； 其次，网中的其次，网中的线路必须最少线路必须最少； 最后，考虑所有线路的最后，考虑所有线路的长度之和最小长度之和最小。最小生成树最小生成树满足上述要求。满足上述要求。上述问题等价于：上述问题等价于：构造网的一棵最小生成树，即：构造网的一棵最小生成树，即：在在 e 条带权的边中选条带权的边中选取取 n-1 条边（不构成回路），使条边（不构成回路），使“权值之和权值之和” 最小。最小。求最小生成树的两个算法：求最小生成树的两个算法：普里姆算

20、法：普里姆算法：适用于求适用于求边稠密的网边稠密的网的最小生成树。的最小生成树。克鲁斯卡尔算法：克鲁斯卡尔算法：适用于求适用于求边稀疏的网边稀疏的网的最小生成的最小生成树。树。假设有连通网假设有连通网 n = v, e ，求，求 n 的最小生成树的最小生成树 t = tv, te 。算法的基本思想算法的基本思想: :一、一、普里姆普里姆(prim)算法算法1. 令令 tv = v , te = ；/从一个顶点从一个顶点v开始开始2. te += min(v, u)，tv += u，其中，其中, vtv, uv-tv;3. 重复步骤重复步骤 2，直到，直到 tv = v。 取图中取图中任意一个顶

21、点任意一个顶点 v 作为生成树的根，之后往生作为生成树的根，之后往生成树上添加成树上添加新的顶点新的顶点 w。在添加的顶点。在添加的顶点 w 和和已经在生已经在生成树上的顶点成树上的顶点v 之间必定存在一条边，并且该边的权值之间必定存在一条边，并且该边的权值在所有连通顶点在所有连通顶点 v 和和 w 之间的边中之间的边中取值最小取值最小。之后继之后继续往生成树上添加顶点，直至生成树上含有续往生成树上添加顶点，直至生成树上含有 n 个顶点个顶点为止。为止。普里姆算法的基本思想普里姆算法的基本思想: :v2v2v0v0v3v3v5v5v4v4v1v13 36 65 52 21 16 65 55 5

22、4 46 6步骤：步骤： (1)初始时，初始时， u=v0，边集合，边集合te= ； (2)在所有在所有 v0 u 、w v-u的边中选择一条的边中选择一条权值最小权值最小的边的边，设这条边为，设这条边为（v0, w）； (3)将边将边 (v0,w) 加入加入te，同时将，同时将w 加入加入u中，而把中，而把w从从v-u中删掉；中删掉； (4)重复重复(2)、(3)，直到，直到u=v为止。为止。v3v3v1v1v4v4v6v6v5v5v2v23 36 65 52 21 16 65 55 54 46 6(1)(1)普里姆算法举例普里姆算法举例 例例1 使用普里姆算法为图使用普里姆算法为图g构造最

23、小生成树。构造最小生成树。u 设最小生成树为：设最小生成树为： t( u， te )图图 g( v, e ) u 构造步骤如下：构造步骤如下：步骤步骤 1 ：初始状态：初始状态 uv1 te= v-u=v2,v3,v4,v5,v6v1v1(1)(1)普里姆算法举例普里姆算法举例v3v3v1v1v4v4v6v6v5v5v2v23 36 65 52 21 16 65 55 54 46 6图图 g( v, e ) 步骤步骤 2 ：v3v3v1v11 1 uv1,v3 v-u= v2,v4,v5,v6(1)(1)普里姆算法举例普里姆算法举例v3v3v1v1v4v4v6v6v5v5v2v23 36 65

24、 52 21 16 65 55 54 46 6图图 g( v, e ) 步骤步骤 3 ：v3v3v1v1v6v61 14 4 uv1, v3, v6 v-u= v2,v4,v5(1)(1)普里姆算法举例普里姆算法举例v3v3v1v1v4v4v6v6v5v5v2v23 36 65 52 21 16 65 55 54 46 6图图 g( v, e ) 步骤步骤 4 ： uv1, v3, v6,v4 v-u= v2,v5v3v3v1v1v4v4v6v61 14 42 2(1)(1)普里姆算法举例普里姆算法举例v3v3v1v1v4v4v6v6v5v5v2v23 36 65 52 21 16 65 55

25、 54 46 6图图 g( v, e ) 步骤步骤 5 ： uv1, v3, v6,v4,v2 v-u= v5v3v3v1v1v4v4v6v6v2v21 14 42 25 5(1)(1)普里姆算法举例普里姆算法举例v3v3v1v1v4v4v6v6v5v5v2v23 36 65 52 21 16 65 55 54 46 6图图 g( v, e ) 步骤步骤 6 ： uv1,v2,v3,v4,v5,v6 uv，结束v3v3v1v1v4v4v6v6v5v5v2v21 14 42 25 53 3(1)(1)普里姆算法举例普里姆算法举例v3v3v1v1v4v4v6v6v5v5v2v23 36 65 52

26、 21 16 65 55 54 46 6图图 g( v, e ) 在算法实现中设置一个在算法实现中设置一个辅助数组辅助数组 closedege，对当前，对当前 v-u 集合中的每个顶点，记录和顶点集集合中的每个顶点，记录和顶点集 u 中顶点相连中顶点相连接的接的代价最小的边代价最小的边；struct vertextype adjvex; / u集中的相邻顶点序号集中的相邻顶点序号 vrtype lowcost; / 边的权值边的权值 closedgemax_vertex_num;例如例如:所得生成树权值和所得生成树权值和 = 14+8+3+5+16+21 = 67abcdegf19514182

27、7168213127aedcbaaa19141814例如例如:e12ee8168d3dd7213c5 5所得生成树权值和所得生成树权值和 = 14+8+3+5+16+21 = 67abcdegf195141827168213127例例2:2:aedcbgf148531621所得生成树权值和所得生成树权值和 = 14+8+3+5+16+21 = 67void minispantree_p (mgraph g, vertextype u) / 用用 prim 算法从顶点算法从顶点 u 出发构造网出发构造网 g 的最小生成树的最小生成树 / 网网 g 用用邻接矩阵邻接矩阵表示表示 k = locat

28、evex( g, u ); max = 100; for ( j = 0; j g.vexnum; +j ) / 辅助数组初始化辅助数组初始化 if ( j != k ) closedgej = u, g.arcskj.adj ; closedgek.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;下页

29、下页 printf ( “(%c, %c)”, closedgek.adjvex, g.vexsk ); / 输出最小生成树的一条边输出最小生成树的一条边 closedgek.lowcost = 0; / k 顶点并入顶点并入 tv 集集 for ( j = 0; j g.vexnum; +j ) / 修改顶点的修改顶点的 lowcast if (g.arcskj.adj closedgej.lowcost) closedgej = g.vexsk, g.arcskj.adj ; / for / minispantree_p练习题练习题1 1 使用普里姆算法为图使用普里姆算法为图g g构造一棵

30、最小构造一棵最小生成树。生成树。4 4 1 17 76 65 52 265653 3606050504040707050503030525245454242图图 g4 4 1 17 76 65 52 23 3505040405050303045454242最小生成树最小生成树练习题练习题2 2 使用使用普里姆算法普里姆算法为图为图g g构造一棵最小构造一棵最小生成树。生成树。算法的基本思想：算法的基本思想：二、克鲁斯卡尔二、克鲁斯卡尔(kruskal)算法算法假设有连通网假设有连通网 n = v, e ，求，求 n 的最小生成树的最小生成树 t = tv, te 。1. 令令 tv = v,

31、te = ； /包含所有顶点包含所有顶点2. te += min(v, u) , (v, u) 是顶点是顶点 v, u 之间的唯一路径之间的唯一路径;3. 重复步骤重复步骤 2，直到，直到 te 中边的条数为中边的条数为 n-1。算法的基本思想：算法的基本思想：考虑问题的出发点考虑问题的出发点: 为使生成树上边的为使生成树上边的权值之和达到权值之和达到最小最小，则应使生成树中，则应使生成树中每一条边的权值尽可能地小每一条边的权值尽可能地小。具体做法具体做法: 先构造一个先构造一个只含只含 n 个顶点的子图个顶点的子图 sg，然后，然后从从权值最小的边权值最小的边开始，若它的添加开始，若它的添加

32、不使不使sg 中产生回路中产生回路，则在则在 sg 上加上这条边，如此重复，直至加上上加上这条边，如此重复，直至加上 n-1 条边条边为止。为止。 步骤：步骤：(1)最小生成树的初始状态为最小生成树的初始状态为只有只有n个顶点而无边个顶点而无边的非连的非连通图通图 t= (v, )。(2)在在e中选取中选取代价最小的边代价最小的边，若该边依附的若该边依附的顶点落在顶点落在t中不同的连通分量上中不同的连通分量上，则将此边加入到，则将此边加入到t中；中； 否则，舍去此边，否则，舍去此边，选取下一条代价最小的边选取下一条代价最小的边。(3)依此类推，直至依此类推，直至t中所有顶点都在同一连通分量上中所有顶点都在同一连通分量上为为止止。例例2 用用克鲁斯卡尔算法克鲁斯卡尔算法构造图构造图g最的小生成树。最的小生成树。(2)(2)克鲁斯卡尔算法克鲁斯卡尔算法v3v3v1v1v4v4v6v6v5v5v2v23 36 65 52 21 16 65 55 54 46 6图图 g= (v, e) 设最小生成树为：设最小生成树为： t( u， te ) 构造步骤如下：构造步骤如下：v3v3v1v1v4v4v6v6v5v5v2v2步骤步骤1：初始状态：初始状态t