图的生成树汇总课件.ppt

1、第十四讲第十四讲 图的生成树图的生成树第1页，共29页。主要内容2.Prim算法算法3.Kruskal算法算法第2页，共29页。要想判定一个无向图是否为连通图，或有几个连通分量，通要想判定一个无向图是否为连通图，或有几个连通分量，通过对无向图遍历即可得到结果。过对无向图遍历即可得到结果。非连通图：需从多个顶点出发进行搜索，而每一次非连通图：需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。访问序列恰为其各个连通分量中的顶点集。连通图：仅需从图中任一顶点出发，进行深度优连通图：仅需从图中

2、任一顶点出发，进行深度优先搜索（或广度优先搜索），便可访问到图中所有先搜索（或广度优先搜索），便可访问到图中所有顶点。顶点。无向图的连通性第3页，共29页。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个连通分量个连通分量);求无向图的连通分量求无向图的连通分量无向图的连通性第4页，共29页。从某顶点出发进行深度优先遍历，并按其所有邻接点都从某顶点出发进行深度优

3、先遍历，并按其所有邻接点都访问（即出栈）的顺序将顶点排列起来。访问（即出栈）的顺序将顶点排列起来。从最后完成访问的顶点出发，沿着以该顶点为头的弧作逆从最后完成访问的顶点出发，沿着以该顶点为头的弧作逆向的深度优先遍历。若不能访问到所有顶点，则从余下的顶向的深度优先遍历。若不能访问到所有顶点，则从余下的顶点中最后访问的那个顶点出发，继续作逆向的深度优先遍历，点中最后访问的那个顶点出发，继续作逆向的深度优先遍历，直至有向图中所有顶点都被访问到为止。直至有向图中所有顶点都被访问到为止。每一次逆向深度优先遍历所访问到的顶点集便是该每一次逆向深度优先遍历所访问到的顶点集便是该有向图的一个强连通分量的顶点集

4、。有向图的一个强连通分量的顶点集。有向图的连通性第5页，共29页。（a）深度优先生成树）深度优先生成树 （b）广度优先生成树广度优先生成树V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V8图的生成树第6页，共29页。由深度优先遍历得到的为深度优先生成树，由深度优先遍历得到的为深度优先生成树，由广度优先遍历得到的为广度优先生成树。由广度优先遍历得到的为广度优先生成树。一个连通图的生成树可能不唯一，由不同的遍一个连通图的生成树可能不唯一，由不同的遍历次序、从不同顶点出发进行遍历都会得到不同历次序、从不同顶点出发进行遍历都会得到不同的生成树。的生成树。对于非连通图，通过图的遍历，将得到

5、的是生成森对于非连通图，通过图的遍历，将得到的是生成森林。林。结论：结论：图的生成树第7页，共29页。生成树的代价：生成树的代价：设设G=（V，E）是一个无向连通网，生成）是一个无向连通网，生成树上各边的权值之和称为该树上各边的权值之和称为该生成树的代价生成树的代价。最小生成树最小生成树(Minimum Spanning Tree,MST)：在图在图G所有生所有生成树中，代价最小的生成树称为成树中，代价最小的生成树称为最小生成树最小生成树。最小生成树的概念可以应用到许多实际问题中。最小生成树的概念可以应用到许多实际问题中。例：在例：在n个城市之间建造通信网络，至少要架设个城市之间建造通信网络，

6、至少要架设n-1条通信条通信线路，而每两个城市之间架设通信线路的造价是不一样的，线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？那么如何设计才能使得总造价最小？最小生成树第8页，共29页。假设假设G=(V,E)是一个无向连通网，是一个无向连通网，U是顶点集是顶点集V的一个非空的一个非空子集。若子集。若(u,v)是一条具有最小权值的边，其中是一条具有最小权值的边，其中uU，vVU，则必存在一棵包含边，则必存在一棵包含边(u,v)的最小生成树。的最小生成树。顶顶点点集集UVUuvvu顶顶点点集集T1T2最小生成树性质第9页，共29页。主要内容1.图的连通性图的连

7、通性3.Kruskal算法算法第10页，共29页。基本思想基本思想：设：设G=(V,E)是具有是具有n个顶点的连通网，个顶点的连通网，T=(U,TE)是是G的最小生成树，的最小生成树，T的的初始状态初始状态为为U=u0（u0V），），TE=，重复执行下述操作：在所有，重复执行下述操作：在所有uU，vV-U的边中找一条代价最小的边的边中找一条代价最小的边(u,v)并入集合并入集合TE，同时同时v并入并入U，直至，直至U=V。关键关键:是如何找到连接是如何找到连接U和和V-U的最短边。的最短边。利用利用MST性质，可以用下述方法构造候选最短边集：对应性质，可以用下述方法构造候选最短边集：对应V-U

8、中的每个顶点，保留从该顶点到中的每个顶点，保留从该顶点到U中的各顶点的最短边。中的各顶点的最短边。普里姆（Prim）算法第11页，共29页。U=A V-U=B,C,D,E,Fcost=(A,B)34,(A,C)46,(A,D),(A,E),(A,F)19 251234192646381725ABEDCF普里姆（Prim）算法第12页，共29页。251234192646381725ABEDCFU=A,F V-U=B,C,D,Ecost=(A,B)34,(F,C)25,(F,D)25,(F,E)26 普里姆（Prim）算法第13页，共29页。251234192646381725ABEDCFU=A,

9、F,C V-U=B,D,Ecost=(A,B)34,(C,D)17,(F,E)26 普里姆（Prim）算法第14页，共29页。251234192646381725ABEDCFU=A,F,C,D V-U=B,Ecost=(A,B)34,(F,E)26 普里姆（Prim）算法第15页，共29页。251234192646381725ABEDCFU=A,F,C,D,E V-U=Bcost=(E,B)12 普里姆（Prim）算法第16页，共29页。251234192646381725ABEDCFU=A,F,C,D,E,B V-U=普里姆（Prim）算法第17页，共29页。数组数组lowcostn：用来保

10、存集合：用来保存集合V-U中各顶点与集合中各顶点与集合U中顶中顶点最短边的权值，点最短边的权值，lowcostv=0表示顶点表示顶点v已加入最小生成树已加入最小生成树中；中；数组数组adjvexn：用来保存依附于该边（集合：用来保存依附于该边（集合V-U中各顶点中各顶点与集合与集合U中顶点的最短边）在集合中顶点的最短边）在集合U中的顶点。中的顶点。数据结构设计数据结构设计表示顶点表示顶点vi和顶点和顶点vk之间的权值为之间的权值为w，其中：其中：vi V-U 且且vk U lowcosti=wadjvexi=k如何用数组如何用数组lowcost和和adjvex表示候选最短边集？表示候选最短边集

11、？普里姆（Prim）算法第18页，共29页。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)25adjvexlowcostA34 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）算法

12、第19页，共29页。1.初始化两个辅助数组初始化两个辅助数组lowcost和和adjvex；2.输出顶点输出顶点u0，将顶点，将顶点u0加入集合加入集合U中；中；3.重复执行下列操作重复执行下列操作n-1次次 3.1 在在lowcost中选取最短边，取中选取最短边，取adjvex中对应的顶点序号中对应的顶点序号k；3.2 输出顶点输出顶点k和对应的权值；和对应的权值；3.3 将顶点将顶点k加入集合加入集合U中；中；3.4 调整数组调整数组lowcost和和adjvex；Prim算法算法伪代码伪代码 普里姆（Prim）算法第20页，共29页。主要内容2.Prim算法算法1.图的连通性图的连通性第

13、21页，共29页。基本思想基本思想：设无向连通网为：设无向连通网为G(V,E)，令，令G的最小生成树的最小生成树为为T(U,TE)，其，其初态为初态为UV，TE，然后，按照，然后，按照边的边的权值由小到大的顺序权值由小到大的顺序，考察，考察G的边集的边集E中的各条边。若被考中的各条边。若被考察的边的两个顶点属于察的边的两个顶点属于T的两个不同的的两个不同的连通分量连通分量，则将此边，则将此边作为最小生成树的边加入到作为最小生成树的边加入到T中，同时把两个连通分量连中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则

14、舍去此边，以免造成回路，如此下去，当连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为中的连通分量个数为1时，此连通分量便为时，此连通分量便为G的一棵最小生成的一棵最小生成树。树。克鲁斯卡尔（Kruskal）算法第22页，共29页。251234192646381725ABEDCFABEDCF连通分量连通分量A,B,C,D,E,F克鲁斯卡尔（Kruskal）算法第23页，共29页。251234192646381725ABEDCFABEDCF连通分量连通分量A,B,C,D,E,F12连通分量连通分量A,B,E,C,D,F克鲁斯卡尔（Kruskal）算法第24页，共29页。2512

15、34192646381725ABEDCFABEDCF12连通分量连通分量A,B,E,C,D,F克鲁斯卡尔（Kruskal）算法17连通分量连通分量A,B,E,C,D,F第25页，共29页。251234192646381725ABEDCFABEDCF连通分量连通分量A,B,E,C,D,F12连通分量连通分量A,F,B,E,C,D19克鲁斯卡尔（Kruskal）算法17第26页，共29页。251234192646381725ABEDCFABEDCF连通分量连通分量A,F,B,E,C,D12连通分量连通分量A,F,C,D,B,E191725克鲁斯卡尔（Kruskal）算法第27页，共29页。2512

16、34192646381725ABEDCFABEDCF连通分量连通分量A,F,C,D,B,E12连通分量连通分量A,F,C,D,B,E19172526克鲁斯卡尔（Kruskal）算法第28页，共29页。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）算法第29页，共29页。