6.2 最小连接问题-最小生成树及其算法

6.2

最小l连接问题——最小生成树及其算法网络建设Net.pas/net.in/net.out【问题描述：】LOI国由n个成员组成（虽然n是常数），所有成员位于一平面坐标系中，每人拥有一台Dell计算机，每台计算机的坐标是已知的，且坐标都是整数。现在，LOI国为加强成员间的交流学习，决定采用每周一人讲课的办法，但这是有硬件要求的，需要对每台计算机之间用一条高速网线相连，并且使所有的计算机都可以直接或间接相连。但分管LOI国的部长莎查·利仕墉(Saca·leesiyon)是个非常抠门的人，想让LOI国用尽量少的资金达到所需的效果(即用最短的网线)，已知两计算机之间的距离为它们的直线距离，求所需网线的最小长度。【输入：】nn行，每行有两个整数x,y表示第i个计算机的坐标为(x,y)【输出：】最短的网线的长度。结果保留3为小数。【输入样例：】6214154353323【输出样例：】9.236数据规模n<=5001<=x,y<=1000返回0123456213456我们解决这种问题所用到的算法就是：最小生成树下面进入正题生成树的概念严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V，E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。

由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。

173010247235含有n个结点的图，从中选n-1条边，保持n-1个点中任意两点是连通的，并且n-1条边的和最小。这n个点和这n-1条边就成为原图的最小生成树。最小生成树的概念朱最学周真学范很学吴司令歪博特最小生成树

求最小生成树的方法主要有以下两种贪心策略：

Prim算法

Kruskal算法

任意结点开始（不妨设为a）构造最小生成树：首先把这个结点包括进生成树里，然后在那些其一个端点已在生成树里、另一端点还未在生成树里的所有边中找出权最小的一条边，并把这条边、包括不在生成树的另一端点包括进生成树，…。依次类推，直至将所有结点都包括进生成树为止。Prim

Prim算法过程bchifaedg488414791067211aidcbhgfe12全部节点都被覆盖，算法结束贴代码//a[i，j]：i到j的边长。//D[i]：结点i到生成树中结点的最短距离//f[i]:true:在生成树中，false：不在生成树中。fori:=1tondobegind[i]:=a[1,i];f[i]:=false;end;f[1]:=true;//放在生成树中

ans:=0;fori:=2tondobeginmin:=maxlongint;forj:=1tondoif(notf[j])and(d[j]<min)thenbeginmin:=d[j];k:=j;end;inc(ans,d[k]);f[k]:=true;

forj:=1tondoif(notf[j])and(a[k,j]<d[j])thend[j]:=a[k,j];//修改dend;是不是感觉和Dijkstra非常相似呢？Prim算法的性能Prim算法的性能取决于如何选取下一个适合条件的最小权值边，因为最小生成树必定有n-1个边，因而选取操作必须进行n-1次。朴素的方法是用邻接矩阵，线性扫描。复杂度为O(n*n)。（用于稠密图）如果用二叉最小堆来实现，可以优化到O(Elgn)。（用于稀疏图）如果使用斐波那契堆，运行时间可以改进为O(E+nlgn)。（用于稀疏图）kruskal算法步骤：1、把图中的边按权值从小到大排序。2、按从小到大的顺序依次向树中加边。在添加每一条边（u，v）时，如果u和V两个点都已在树中，一旦添加，就回构成回路，所以放弃该边，在向后找下一条边。3、直到添加n-1条边。

Kruskal算法在实现过程中的关键和难点在于：如何判断欲加入的一条边是否与生成树中已保留的边形成回路？怎么搞？并查集！Kruskal算法过程bchifaedg488414791067211aidcbhgfe12构成环路构成环路构成环路全部节点都被覆盖，算法结束贴代码typenode=recorddata:integer;u,v:integer;end;vare:array[1..maxn*(maxn-1)div2]ofnode;//边

f:array[1..maxn]ofinteger;//父亲接点

n,m:integer;ans:integer;readln(n);m:=0;whilenotseekeofdobeginreadln(i,j,k);inc(m);e[m].data:=k;e[m].u:=i;e[m].v:=j;end;procedurekruskal;vari:integer;begin

qsort;fori:=1tondof[i]:=0;//初始化根为0ans:=0;fori:=1tomdounion(e[i]);end;procedureunion(p:node);//检查边p是否能加到生成树中

varx,y:integer;beginx:=find(p.u);//找u的根

y:=find(p.v);//找v的根

ifx<>ythen//不同根，构不成环，加入

begininc(ans,p.data);f[y]:=x;//根合并

end;end;functionfind(i:integer):integer;//查找i的父亲

beginiff[i]=0thenexit(i);//i是根

iff[f[i]]=0thenexit(f[i]);//i的父亲是根

find:=find(f[i]);//递归查找

f[i]:=find;//路径压缩

end;Kruskal算法的性能Kruskal也需要进行n-1次选取操作，它的选取范围是整个图，因而可以用O(ElgE)的时间对所有的边进行排序。从这个有序的排列依次选取，若选取的边的加入不能构成回路，则加入。否则对排列的下一个边进行相同操作。直到选取了n-1个边为止。

对prim算法与kruskal算法比较和总结1)PrimandKruskal

算法的空间比较数据给的情况不同空间有所不同当点少边多的时候如1000个点500000条边这样BT的数据用prim做就要开一个1000*1000的二维数组而用kruskal做只须开一个500000的数组，恐怖吧500000跟1000*1000比较相差一半。当点多边少的时候如1000000个点2000条边像这中BT数据就是为卡内存而存在的，如果用prim做你想开一个1000000*1000000的二维数组没门内存绝对爆挂你。而像这种情况用kruskal只须开一个2000的数组绝对赚到了。

样例ZQM版：有没有道理？2)PrimandKruskalandKruskal+快排算法的时间比较prim在跟普通的kruskal比较空间是肯定没有普通的kruskal来的好。但时间方面的话prim就比普通kruskal来的更恐怖一些，用prim时间比普通的kruskal快20倍。在这时我就想如果那数据变态的很，用普通的kruskal绝对超时，用prim绝对爆内存那就惨了。这时惟有改进算法。prim算法从中砍内存，怎么砍，换一个超大内存的电脑，你去哪找啊。拿刀砍，开玩笑。方法一放弃。方法二在改进kruskal算法从中砍时间，普通的kruskal在选择感染了的边的时候还要进行搜索其所有被感染