最小生成树算法及应用

《最小生成树算法及应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最小生成树算法及应用一、生成树的概念若图是连通的无向图或强连通的有向图，则从图中任意一个顶点出发调用一次bfs或dfs后，便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs，亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图，称为原图的生成树。对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后，一般不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其

2、它顶点，还需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs或dfs，这样得到的是生成森林。由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。最小生成树算法及应用最小生成树算法及应用二、求图的最小生成树算法严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V，E’），且边集E’能将图中所有顶

3、点连通又不形成回路，则称子图G’是图G的一棵生成树。对于带权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树，称为图的最小生成树。求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。最小生成树算法及应用例1、城市公交网[问题描述]有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最

4、少。[输入]n（城市数，1<=n<=100）；e（边数）；以下e行，每行3个数i,j,wij，表示在城市i,j之间修建高速公路的造价。[输出]n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。最小生成树算法及应用[举例]下面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20和33，前者比后者好一些，但并不是最小生成树，最小生成树的权和为19。[问题分析]出发点：具有n个顶点的带权连通图，其对应的生成树有n-1

5、条边！那么选哪n-1条边呢？设图G的度为n，G=（V，E）我们介绍两种基于贪心的算法，Prim算法和Kruskal算法。最小生成树算法及应用1、用Prim算法求最小生成树的思想如下：①设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集；②选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S；③重复下列操作，直到选取了n-1条边：选取一条权值最小的边（X，Y），其中X∈S，not(Y∈S)；将顶点Y加入集合S，边（X，Y）加入集合TE；④得到最小生成树T=（S，TE）。如何证明

6、Prim算法的正确性呢？提示：用反证法。因为操作是沿着边进行的，所以数据结构宜采用边集数组表示法。最小生成树算法及应用①从文件中读入图的邻接矩阵g；②边集数组elist初始化；Fori:=1Ton-1DoBeginelist[i].fromv:=1；elist[i].endv:=i+1；elist[i].weight:=g[1,i+1]；End；③求出最小生成树的n-1条边；Fork:=1Ton-1DoBeginmin:=maxint；m:=k；Forj:=kTon-1Do{查找权值最小的一条边}If

7、elist[j].weightkThenBegint:=elist[k]；elist[k]:=elist[m]；elist[m]:=t；End；{把权值最小的边调到第k个单元}j:=elist[k].endv；{j为新加入的顶点}Fori:=k+1Ton-1Do{修改未加入的边集}Begins:=elist[i].endv；w:=g[j,s]；Ifw

8、t[i].weight:=w；elist[i].fromv:=j；End；End；End；④输出；——Prim算法的实现最小生成树算法及应用2、用Kruskal算法求最小生成树的思想如下：设最小生成树为T=（V，TE），设置边的集合TE的初始状态为空集。将图G中的边按权值从小到大排好序，然后从小的开始依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；若选取的边使生成树形成回路，则将其舍弃；如此进行下去，直到TE中包含n-1条