知识点回顾 图的深度优先和广度优先遍历思想 图的深度优先遍历算法（用邻接表作为存储结构） 图的广度优先遍历算法（用邻接矩阵作为存储结构） 核心：递归思想 图的广度优先遍历算法（用邻接矩阵作为存储结构） 核心：循环队列

第六章 图 6.1 图的定义和术语 6.2 图的存储结构 6.3 图的遍历 6.4 图的连通性问题 6.5 有向无环图及其应用 6.6 最短路径

导入 假设你是电信的实施工程师，需要为一个镇的九个村庄架设通信网络做设计，领导要求你必须用最小的成本完成这次任务。 你说怎么办?

6.4 图的连通性问题 6.4.1 无向图的连通分量和生成树 若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点； 6.4 图的连通性问题 6.4.1 无向图的连通分量和生成树 若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点； 若图是非连通的或非强连通图，则需从图中多个顶点出发搜索访问，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为每个连通分量中的顶点集。 如:下页

D E A B C F J L M G H I K A B C F J L M G H I K D E

深度优先搜索遍历算法及广度优先搜索遍历算法中遍历图过程中历经边的集合和顶点集合一起构成连通图的极小连通子图。它是连通图的一颗生成树。 生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。 由深度优先搜索遍历得到的生成树，称为深度优先生成树，由广度优先搜索遍历得到的生成树，称为广度优先生成树。图8-13中无向图G7的两种生成树见 图8-19(下页)。

例1 ：画出下图的生成树 1 2 3 4 v4 v3 v2 v1 v0 v0 v1 v2 v4 v3 邻接表 无向连通图 v0 v0 1 2 3 4 ^ 1 3 4 2 v4 v3 v2 v1 v0 v0 v1 v2 v4 v3 邻接表 无向连通图 v0 v0 DFS生成树 BFS生成树 v3 v1 v3 v4 v2 v4 v2 v1

2．生成森林 若一个图是非连通图或非强连通图，但有若干个连通分量或若干个强连通分量，则通过深度优先搜索遍历或广度优先搜索遍历，不可以得到生成树，但可以得到生成森林，且若非连通图有 n 个顶点，m 个连通分量或强连通分量，则可以遍历得到m棵生成树，合起来为生成森林，森林中包含n-m条树边。 生成森林可以利用非连通图的深度优先搜索遍历或非连通图的广度优先搜索遍历算法得到。 3． 最小生成树 在一般情况下，图中的每条边若给定了权，这时，我们所关心的不是生成树，而是生成树中边上权值之和。若生成树中每条边上权值之和达到最小，称为最小生成树。

例2：画出下图的生成森林（或极小连通子图） D E A B C F J L M G H I K 这是一个无向非连通图 求解步骤： Step1:先求出邻接矩阵或邻接表； Step2:写出DFS或BFS结果序列； Step3:画出对应子图或生成森林。 注：亦可由邻接矩阵或邻接表直接画出生成森林 下面选用邻接表方式来求深度优先搜索生成森林

先写出邻接表（或邻接矩阵）： 再写出DFS结果（3次）ABMJLCF DE GHKI 5 M 12 L K 10 J 9 I 8 H 7 G 11 5 M 12 L K 10 J 9 I 8 H 7 G 6 F E 4 D 3 C 2 B 1 A ^ 最小连通！ A B C F J L M 子图1： 子图2： D E G H I K 子图3：

子图 (或连通分量) A B C F J L M G H I K D E A B C F J L M G H I K D E 生成森林

2. 求最小生成树 首先明确： 使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。 2. 求最小生成树 首先明确： 使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。 按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。 目标： 在网络的多个生成树中，寻找一个各边权值之和最小的生成树。 构造最小生成树的准则 必须只使用该网络中的边来构造最小生成树； 必须使用且仅使用n-1条边来联结网络中的n个顶点； 不能使用产生回路的边。 边的权值之和最小。

典型用途： 欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2 条线路，那么，如何选择n–1条线路，使总费用最少？ 数学模型： 顶点———表示城市，有n个； 边————表示线路，有n–1条； 边的权值—表示线路的经济代价； 连通网——表示n个城市间通信网。 显然此连通网是一个生成树！ 问题抽象： n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST(Minimum cost Spanning Tree)

MST 性质： 假设 G = {V, { E } } 是一个连通图，U 是结点集合 V 的一个非空子集。若 ( u, v ) 是一条代价最小的边，且 u 属于 U , v 属于 V -- U，则必存在一棵包括边 ( u, v ) 在内的最小代价生成树。 证明：假定存在一棵不包括边 ( u, v ) 在内的最小代价生成树，设其为 T。将边( u, v ) 添加到树 T ，则形成一条包含 ( u, v ) 的回路。因此，必定存在另一条边 ( u‘ ，v‘ ) ，且 u’ 属于 U , v ‘ 属于 V - U。删去边 ( u‘ ，v‘ ) ，得到另一棵生成树 T ‘ ; 因为边 ( u, v ) 的代价小于边 ( u‘ ，v‘ ) 的代价，所以新的生成树T ‘将是代价最小的树。和原假设矛盾。 T v u v’ u’

7 1 6 5 4 3 2 7 5 9 13 24 10 17 12 18 1 5 6 4 3 2 7 9 10 13

6.4.3 最小生成树 下面将介绍求最小生成树的两种方法：普里姆算法和克鲁斯卡尔算法。 1. 普里姆算法 普里姆(prim)算法思想 （归并顶点，适用于稠密网） 下面仅讨论无向网的最小生成树问题。 普里姆方法的思想是：在图中任取一个顶点K作为开始点，令U={k}，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离, 使之保持最小，再重复此过程，直到W为空集止。求解过程参见图8-20 。

例 1 6 5 4 3 2 1 1 3 1 6 3 4 1 6 4 3 2 1 6 4 3 2 5 1 6 5 4 3 2

假设开始顶点就选为顶点1，故首先有U={1}，W={2，3，4，5，6} i 1 2 3 4 5 6 closest[i] lowcost[i] ∞ closest用于存放顶点序号 lowest存放权值

i 1 2 3 4 5 6 closest[i] lowcost[i] i 1 2 3 4 5 6 closest[i] lowcost[i]

i 1 2 3 4 5 6 closest[i] lowcost[i] i 1 2 3 4 5 6 closest[i] lowcost[i] i 1 2 3 4 5 6 closest[i] lowcost[i]

/*赋初值*/ #include "stdio.h" #define max 32767 #define n 6 void prim(int matrix[n][n],int v0) { int i,j,k,min,lowcost[n],closet[n]; /*赋初值*/ for(i=0; i<=n-1;i++) if (i!=v0){lowcost[i]=matrix[v0][i];closet[i]=v0;} else lowcost[i]=0; for(i=1;i<=n-1;i++) { /*在lowcost中找大于0最小值，记录其下标k，将lowcost[k]=0 */ for(min=max,j=0;j<=n-1;j++) if (min>lowcost[j]&&lowcost[j]!=0) {min=lowcost[j];k=j;} printf("%d->%d:%d\n",k,closet[k],min); lowcost[k]=0; /*更新lowcost[j]的值 */ for(j=0;j<=n-1;j++) if(matrix[k][j]<lowcost[j] && lowcost[j]!=0) {lowcost[j]=matrix[k][j]; closet[j]=k;} }

main( ) { int matrix[n][n]={{max,6,1,5,max,max},{6,max,5,max,3,max},{1,5,max,max,6,4}, {5,max,max,max,max,2},{max,3,6,max,max,6},{max,max,4,2,6,max}}; /*构造矩阵*/ prim(matrix,5); } 分析:Prim算法的时间复杂度为O(n2)，它适合稠密图。

考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。 2. 克鲁斯卡尔（kruskal）算法 考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。

克鲁斯卡尔算法基本思想 克鲁斯卡尔算法的基本思想是：将图中所有边按权值递增顺序排列，依次选定取权值较小的边，但要求后面选取的边不能与前面选取的边构成回路，若构成回路，则放弃该条边，再去选后面权值较大的边，n个顶点的图中，选够n-1条边即可。 例如，对图8-20（a） 中无向网，用克鲁斯卡尔算法求最小生成树的过程见图8-22。

分析: 克鲁斯卡尔算法的时间复杂度为O(eloge)，它适合稀疏图。

例如:克鲁斯卡尔算法 a a b b c c e e g g d d f f 19 19 5 5 12 12 14 14 7 7 18 18 16 16 8 8 3 3 g g d d 27 21 21 f f

例如:普里姆(prim)算法 a a b b c c e e g g d d f f 所得生成树权值和 19 a a b b 5 5 12 14 14 c c 7 18 e e 8 8 16 16 3 3 g g d d 27 21 21 f f 所得生成树权值和 = 14+8+3+5+16+21 = 67

结论 注：一个网中，若有权值相同的边，则其最小生成树不一定唯一；若所有边的权值均不相同，则其最小生成树是唯一的。

小结 生成树、生成森林 概念、生成过程 最小生成树 概念、 MST 性质 普里姆算法和克鲁斯卡尔算法

作业 已知无向图G的邻接矩阵， 按要求完成下列各题。 给出无向图G中各顶点的度数； 给出无向图G的邻接表； 分别给出应用Kruskal和Prim算法构造最小生成树的过程。