《最小生成树算法及应用讲解》由会员分享，可在线阅读，更多相关《最小生成树算法及应用讲解（17页珍藏版）》请在金锄头文库上搜索。
1、最小生成树算法及应用 一、生成树的概念 若图是连通的无向图或强连通的有向图，则从图中任意一个顶点出发调用一 次bfs或dfs后，便可以系统地访问图中所有顶点；若图是有根的有向图，则从根 出发通过调用一次dfs或bfs，亦可系统地访问所有顶点。在这种情况下，图中所 有顶点加上遍历过程中经过的边所构成的子图，称为原图的生成树。 对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点 出发，调用一次bfs或dfs后，一般不能系统地访问所有顶点，而只能得到以出发 点为根的连通分支（或强连通分支）的生成树。要访问其它顶点，还需要从没有 访问过的顶点中找一个顶点作为起始点，再次调用bfs或df
2、s，这样得到的是生成 森林。 由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同 的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。 可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。 最小生成树算法及应用 最小生成树算法及应用 二、求图的最小生成树算法 严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和 一部分边E构成一个子图G，即G=（V， E），且边集E能将图中所有顶 点连通又不形成回路，则称子图G是图G的一棵生成树。 对于带权连通图，生成树的权即为生成树中所有边上的权值总和，权值最 小的生成树，称为图的最小生成树。 求图的
3、最小生成树具有很高的实际应用价值，比如下面的这个例题。 最小生成树算法及应用 例1、城市公交网 问题描述 有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边 上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特 点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联 系起来，问如何设计可使得工程的总造价最少。 输入 n（城市数，1=n=100）； e（边数）； 以下e行，每行3个数i,j,wij，表示在城市i,j之间修建高速公路的造价。 输出 n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。 最小生成树算法及应用 举例 下
4、面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行 深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20和33，前者比后 者好一些，但并不是最小生成树，最小生成树的权和为19。 问题分析 出发点：具有n个顶点的带权连通图，其对应的生成树有n-1条边！ 那么选哪n-1条边呢？ 设图G的度为n，G=（V，E） 我们介绍两种基于贪心的算法，Prim算法和Kruskal算法。 最小生成树算法及应用 1、用Prim算法求最小生成树的思想如下： 设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集； 选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S
5、； 重复下列操作，直到选取了n-1条边： 选取一条权值最小的边（X，Y），其中XS，not (YS)； 将顶点Y加入集合S，边（X，Y）加入集合TE； 得到最小生成树T =（S，TE） 。 如何证明Prim算法的正确性呢？提示：用反证法。 因为操作是沿着边进行的，所以数据结构宜采用边集数组表示法 。 最小生成树算法及应用 从文件中读入图的邻接矩阵g； 边集数组elist初始化； For i:=1 To n-1 Do Begin elisti.fromv:=1；elisti.endv:=i+1；elisti.weight:=g1,i+1； End； 求出最小生成树的n-1条边； For k:=1
6、 To n-1 Do Begin min:=maxint；m:=k； For j:=k To n-1 Do 查找权值最小的一条边 If elistj.weightmin Then Begin min:=elistj.weight；m:=j；End； If mk Then Begin t:=elistk；elistk:=elistm；elistm:=t；End； 把权值最小的边调到第k个单元 j:=elistk.endv； j为新加入的顶点 For i:=k+1 To n-1 Do 修改未加入的边集 Begin s:=elisti.endv； w:=gj,s； If welisti.weight
7、 Then Begin elisti.weight:=w；elisti.fromv:=j；End； End； End； 输输出； Prim算法的实现 最小生成树算法及应用 2、用Kruskal算法求最小生成树的思想如下： 设设最小生成树为树为 T=（V，TE），设设置边边的集合TE的初始状态为态为 空集。将图图G中 的边边按权值权值 从小到大排好序，然后从小的开始依次选选取，若选选取的边边使生成树树T不 形成回路，则则把它并入TE中，保留作为为T的一条边边；若选选取的边边使生成树树形成回路 ，则则将其舍弃；如此进进行下去，直到TE中包含n-1条边为边为 止。最后的T即为为最小生成 树树。 如何
8、证明呢？ 最小生成树算法及应用 Kruskal算法在实现过实现过 程中的关键键和难难点在于：如何判断欲加入的一条边边 是否与生成树树中已保留的边边形成回路？ 我们们可以将顶顶点划分到不同的集合中，每个集合中的顶顶点表示一个无回 路的连连通分量，很明显显算法开始时时，把所有n个顶顶点划分到n个集合中，每个 集合只有一个顶顶点，表明顶顶点之间间互不相通。当选选取一条边时边时 ，若它的两个 顶顶点分属于不同的集合，则则表明此边连边连 通了两个不同的连连通分量，因每个连连 通分量无回路，所以连连通后得到的连连通分量仍不会产产生回路，因此这这条边应边应 该该保留，且把它们们作为为一个连连通分量，即把它的
9、两个顶顶点所在集合合并成一 个集合。如果选选取的一条边边的两个顶顶点属于同一个集合，则则此边应该边应该 舍弃， 因为为同一个集合中的顶顶点是连连通无回路的，若再加入一条边则边则 必然产产生回路 。 就是并查集的思想。 最小生成树算法及应用 将图的存储结构转换成边集数组表示的形式elist，并按照权值从小到大排好序； 设数组C1n-1用来存储最小生成树的所有边，Ci是第i次选取的可行边在排好序的elist中的下标； 设一个数组S1n，Si都是集合，初始时Si= i 。 i:=1；获取的第i条最小生成树的边 j:=1；边集数组的下标 While i=n-1 Do Begin For k:=1 To
10、 n Do Begin 取出第j条边，记下两个顶点分属的集合序号 If elistj.fromv in sk Then m1:=k； If elistj.endv in sk Then m2:=k； End； If m1m2 Then Begin 找到的elist第j条边满足条件，作为第i条边保留 Ci:=j；i:=i+1； sm1:=sm1+sm2；合并两个集合 sm2:= ； 另一集合置空 End； j:=j+1； 取下条边，继续判断 End； 输输出最小生成树树的各边边：elistCi Kruskal算法的实现 最小生成树算法及应用 二、求图的最小生成树算法小结 都是基于贪心算法时间复杂
11、度均为O（n*n） Prim算法和Kruskal算法 三、应用举例 例2、最优布线问题（wire.?） 学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们时 间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。 当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据 的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接 。 现在由你负责连接这些计算机，你的任务是使任意两台计算机都连通（不管是直接的或间接的）。 输入格式 输入文件第一行为整数n（2=n
12、0 then cp：=1 else cp：=-1； nend；cp nfunction dist(a，b：integer)：longint； 计算第a条机器蛇和第b条机器蛇间 的距离，若ab之间有屏蔽，则距离设为无穷大 nvar n i：integer； nbegin n dist：=oo； n for i：=1 to m do 如果a到b穿过第i个屏蔽，则返回无穷大 n if (cp(w1i，w2i，sa)*cp(w1i，w2i，sb)=-1) and n (cp(sa，sb，w1i)*cp(sa，sb，w2i)=-1) then exit； n dist：=sqr(sa.x-sb.x)+s
13、qr(sa.y-sb.y)； nend； dist nbegin n read(n)； 读入数据 n for i：=1 to n do with si do read(x，y)； n read(m)； n for i：=1 to m do read(w1i.x，w1i.y，w2i.x，w2i.y)； n用Prim算法求最小生成树 n fillchar(ba，sizeof(ba)，0)； 所有机器蛇未访问 n for i：=2 to n do di：=oo； 最短边长序列初始化 n d1：=0 ；ans：=0； 从机器蛇1出发,通信网的最短长度初始化 n for i：=1 to n do beg
14、in 访问n条机器蛇 n min：=oo；在所有未访问的机器蛇中寻找与已访问的机器蛇相连且具有最短边长 的机器蛇k n for j：=1 to n do if not baj and (djmin) then begin n k：=j； min：=dj； n end；then n if min=oo then begin ans：=-1； break； end；then若这样的机器蛇不存在， 则无解退出 ans：=ans+sqrt(min)； bak：=true； 最短边长计入通信网,机器蛇k已访问 n for j：=1 to n do 机器蛇k出发的所有不受屏蔽的边中，寻找边长最短的（k，j） n begin min：=dist(k，j)； if mindj then dj：=min； end；for nend；for n writeln(ans：0：3)； 输出通信网的最短长度 nend.main
