1、第十四讲第十四讲 图的生成树图的生成树 主要内容2.Prim算法算法3.Kruskal算法算法 要想判定一个无向图是否为连通图，或有几个连通要想判定一个无向图是否为连通图，或有几个连通分量，通过对无向图遍历即可得到结果。分量，通过对无向图遍历即可得到结果。非连通图：需从多个顶点出发进行搜索，而每一非连通图：需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。点访问序列恰为其各个连通分量中的顶点集。连通图：仅需从图中任一顶点出发，进行深度优连通图：仅需从图中任一顶点出发，进行深度优先搜索（
2、或广度优先搜索），便可访问到图中所先搜索（或广度优先搜索），便可访问到图中所有顶点。有顶点。无向图的连通性 1.count=0;2.for(图中每个顶点图中每个顶点v)2.1 if(v尚未被访问过尚未被访问过)2.1.1 count+;2.1.2 从从v出发遍历该图；出发遍历该图；3.if(count=1)printf(图是连通的图是连通的“);else printf(图中有图中有count个连通分量个连通分量);求无向图的连通分量求无向图的连通分量无向图的连通性 从某顶点出发进行深度优先遍历，并按其所有邻从某顶点出发进行深度优先遍历，并按其所有邻接点都访问（即出栈）的顺序将顶点排列起来。接点
3、都访问（即出栈）的顺序将顶点排列起来。从最后完成访问的顶点出发，沿着以该顶点为头从最后完成访问的顶点出发，沿着以该顶点为头的弧作逆向的深度优先遍历。若不能访问到所有顶的弧作逆向的深度优先遍历。若不能访问到所有顶点，则从余下的顶点中最后访问的那个顶点出发，点，则从余下的顶点中最后访问的那个顶点出发，继续作逆向的深度优先遍历，直至有向图中所有顶继续作逆向的深度优先遍历，直至有向图中所有顶点都被访问到为止。点都被访问到为止。每一次逆向深度优先遍历所访问到的顶点集便是每一次逆向深度优先遍历所访问到的顶点集便是该有向图的一个强连通分量的顶点集。该有向图的一个强连通分量的顶点集。有向图的连通性 （a）深度
4、优先生成树）深度优先生成树 （b）广度优先生成树广度优先生成树V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V8图的生成树 由深度优先遍历得到的为深度优先生成树，由深度优先遍历得到的为深度优先生成树，由广度优先遍历得到的为广度优先生成树。由广度优先遍历得到的为广度优先生成树。一个连通图的生成树可能不唯一，由不同的一个连通图的生成树可能不唯一，由不同的遍历次序、从不同顶点出发进行遍历都会得到遍历次序、从不同顶点出发进行遍历都会得到不同的生成树。不同的生成树。对于非连通图，通过图的遍历，将得到的是对于非连通图，通过图的遍历，将得到的是生成森林。生成森林。结论：结论：图的生成树 生成树
5、的代价：生成树的代价：设设G=（V，E）是一个无向连通网，）是一个无向连通网，生成树上各边的权值之和称为该生成树上各边的权值之和称为该生成树的代价生成树的代价。最小生成树最小生成树(Minimum Spanning Tree,MST)：在图在图G所有生成树中，代价最小的生成树称为所有生成树中，代价最小的生成树称为最小生成树最小生成树。最小生成树的概念可以应用到许多实际问题中。最小生成树的概念可以应用到许多实际问题中。例：在例：在n个城市之间建造通信网络，至少要架设个城市之间建造通信网络，至少要架设n-1条条通信线路，而每两个城市之间架设通信线路的造价是通信线路，而每两个城市之间架设通信线路的造
6、价是不一样的，那么如何设计才能使得总造价最小？不一样的，那么如何设计才能使得总造价最小？最小生成树 假设假设G=(V,E)是一个无向连通网，是一个无向连通网，U是顶点集是顶点集V的一的一个非空子集。若个非空子集。若(u,v)是一条具有最小权值的边，其是一条具有最小权值的边，其中中uU，vVU，则必存在一棵包含边，则必存在一棵包含边(u,v)的最的最小生成树。小生成树。顶顶点点集集UVUuvvu顶顶点点集集T1T2最小生成树性质 主要内容1.图的连通性图的连通性3.Kruskal算法算法 基本思想基本思想：设：设G=(V,E)是具有是具有n个顶点的连通网，个顶点的连通网，T=(U,TE)是是G的
7、最小生成树，的最小生成树，T的的初始状态初始状态为为U=u0（u0V），），TE=，重复执行下述操作：，重复执行下述操作：在所有在所有uU，vV-U的边中找一条代价最小的边的边中找一条代价最小的边(u,v)并入集合并入集合TE，同时，同时v并入并入U，直至，直至U=V。关键关键:是如何找到连接是如何找到连接U和和V-U的最短边的最短边。利用利用MST性质，可以用下述方法构造候选最短边集：性质，可以用下述方法构造候选最短边集：对应对应V-U中的每个顶点，保留从该顶点到中的每个顶点，保留从该顶点到U中的各顶中的各顶点的最短边。点的最短边。普里姆（Prim）算法 U=A V-U=B,C,D,E,Fc
8、ost=(A,B)34,(A,C)46,(A,D),(A,E),(A,F)19 251234192646381725ABEDCF普里姆（Prim）算法 251234192646381725ABEDCFU=A,F V-U=B,C,D,Ecost=(A,B)34,(F,C)25,(F,D)25,(F,E)26 普里姆（Prim）算法 251234192646381725ABEDCFU=A,F,C V-U=B,D,Ecost=(A,B)34,(C,D)17,(F,E)26 普里姆（Prim）算法 251234192646381725ABEDCFU=A,F,C,D V-U=B,Ecost=(A,B)3
9、4,(F,E)26 普里姆（Prim）算法 251234192646381725ABEDCFU=A,F,C,D,E V-U=Bcost=(E,B)12 普里姆（Prim）算法 251234192646381725ABEDCFU=A,F,C,D,E,B V-U=普里姆（Prim）算法 数组数组lowcostn：用来保存集合：用来保存集合V-U中各顶点与集合中各顶点与集合U中顶点最短边的权值，中顶点最短边的权值，lowcostv=0表示顶点表示顶点v已加入已加入最小生成树中；最小生成树中；数组数组adjvexn：用来保存依附于该边（集合：用来保存依附于该边（集合V-U中各中各顶点与集合顶点与集合U
10、中顶点的最短边）在集合中顶点的最短边）在集合U中的顶点。中的顶点。数据结构设计数据结构设计表示顶点表示顶点vi和顶点和顶点vk之间的权值为之间的权值为w，其中：其中：vi V-U 且且vk U lowcosti=wadjvexi=k如何用数组如何用数组lowcost和和adjvex表示候选最短边集？表示候选最短边集？普里姆（Prim）算法 i 数组数组B(i=1)C(i=2)D(i=3)E(i=4)F(i=5)UV-U输出输出adjvexlowcostA34A46AAA19AB,C,D,E,F(A F)19adjvexlowcostA34F25F25F26 A,FB,C,D,E(F C)25a
11、djvexlowcostA34 C17F26 A,F,CB,D,E(C D)17adjvexlowcostA34 F26 A,F,C,DB,E(F E)26adjvexlowcostE12 A,F,C,D,EB(E B)12adjvexlowcost A,F,C,D,E,B 普里姆（Prim）算法 1.初始化两个辅助数组初始化两个辅助数组lowcost和和adjvex；2.输出顶点输出顶点u0，将顶点，将顶点u0加入集合加入集合U中；中；3.重复执行下列操作重复执行下列操作n-1次次 3.1 在在lowcost中选取最短边，取中选取最短边，取adjvex中对应的顶点序号中对应的顶点序号k；3.
12、2 输出顶点输出顶点k和对应的权值；和对应的权值；3.3 将顶点将顶点k加入集合加入集合U中；中；3.4 调整数组调整数组lowcost和和adjvex；Prim算法算法伪代码伪代码 普里姆（Prim）算法 主要内容2.Prim算法算法1.图的连通性图的连通性 基本思想基本思想：设无向连通网为：设无向连通网为G(V,E)，令，令G的最小生的最小生成树为成树为T(U,TE)，其，其初态为初态为UV，TE，然后，然后，按照按照边的权值由小到大的顺序边的权值由小到大的顺序，考察，考察G的边集的边集E中的各中的各条边。若被考察的边的两个顶点属于条边。若被考察的边的两个顶点属于T的两个不同的的两个不同的
13、连连通分量通分量，则将此边作为最小生成树的边加入到，则将此边作为最小生成树的边加入到T中，同中，同时把两个连通分量连接为一个连通分量；若被考察边时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当造成回路，如此下去，当T中的连通分量个数为中的连通分量个数为1时，时，此连通分量便为此连通分量便为G的一棵最小生成树。的一棵最小生成树。克鲁斯卡尔（Kruskal）算法 251234192646381725ABEDCFABEDCF连通分量连通分量A,B,C,D,E,F克鲁斯卡尔（Kruskal）
14、算法 251234192646381725ABEDCFABEDCF连通分量连通分量A,B,C,D,E,F12连通分量连通分量A,B,E,C,D,F克鲁斯卡尔（Kruskal）算法 251234192646381725ABEDCFABEDCF12连通分量连通分量A,B,E,C,D,F克鲁斯卡尔（Kruskal）算法17连通分量连通分量A,B,E,C,D,F 251234192646381725ABEDCFABEDCF连通分量连通分量A,B,E,C,D,F12连通分量连通分量A,F,B,E,C,D19克鲁斯卡尔（Kruskal）算法17 251234192646381725ABEDCFABEDCF
15、连通分量连通分量A,F,B,E,C,D12连通分量连通分量A,F,C,D,B,E191725克鲁斯卡尔（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算法算法伪代码伪代码克鲁斯卡尔（Kruskal）算法
