图的最小生成树-prim算法

1基本图算法陈嘉庆最小生成树问题最小生成树一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。最小生成树算法的目标：一个n个点的图，选若干条边（一定是n-1条）使得图连在一起，并且所有选中的边的长度和最小。最小生成树其实是最小权重生成树的简称。3最小生成树生成树和最小生成树有许多重要的应用。例如：要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。4Prim算法最小生成树---Prim算法Prim普里姆算法1).输入：一个加权连通图，其中顶点集合为V，边集合为E；2).初始化：Vnew={x}，其中x为集合V中的任一节点（起始点），Enew={},为空；3).重复下列操作，直到Vnew=V：a.在集合E中选取权值最小的边u,v，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；b.将v加入集合Vnew中，将u,v边加入集合Enew中；4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。64最小生成树问题：修建一个连接各个小区与供应站点之间的管道使得造价成本最低，即构造一颗最小生成树。但是如何求解？4.1prim算法1.基本思想在满足如下条件的过程中选出一条最小的边：一端已选，另一端未选。因此，该算法需要给出起点，以作为已选顶点。2.实例对右图所示图，用Prim算法求最小生成树。1746125349129915610374最小生成树46125349129915617103961253412991561710439612534129915617104396125341299156171043961253412991561710439612534129915617104384最小生成树--求解过程的表格化求解已选顶点集U顶点1候选边顶点2候选边顶点3候选边顶点4候选边顶点5候选边顶点6候选边{1}{1,6}{1,6,5}{1,6,5,4}{1,6,5,4,3}{1,6,5,4,3,2}}(1,2)/12(1,3)/∞(1,4)/∞(1,5)/9(1,6)/9(1,2)/12(6,2)/15(6,3)/17(6,4)/20(1,5)/9(6,5)/9(6,4)/20(5,4)/4(1,2)/12(6,2)/15(6,3)/17(1,2)/12(6,2)/15(6,3)/17(4,3)/3(1,2)/12(6,2)/15(3,2)/61746125349129915610394最小生成树——Prim算法练习求下图的最小生成树：1235412354435323136已选顶点集合U顶点1候选边顶点2候选边顶点3候选边顶点4候选边顶点5候选边{1}(1,2)/3(1,3)/3(1,4)/4(1,5)/∞{1,3}(3,2)/5(3,4)/2(3,5)/6{1,3,4}(4,2)/∞(4,5)/1{1,3,4,5}(5,2)/3{1,3,4,5,2}13425Prim最小生成树注：最小生成树不唯一,但权值之和相同。104最小生成树3.算法Prim算法的简要描述（设起点为v0）：设置各候选边(v0,vi)；for(i=1;i=n-1;i++){从候选边中找出权值最小的边(v,vk)；//其中v已选边，vk未选将vk设置为已选顶点；调整候选边集合----调整新入选顶点和未选顶点之间的边的集合}由此可知，需要考虑如下几个方面的实现：（1）已选顶点的标识：可用数组来或集合来存储（或形式化描述）。（2）候选边的存储：虽然每个顶点可能对应多个候选边，但只要最小的一个，因此，用一个数组也可以，不妨用edges[]（下标用1-n即可）114最小生成树①初始化候选边数组edges[]；②U={v0}；③for(i=1;i=n-1;i++){k=最小候选边的未选的一端；U=U+{k}；以k修改edges[]；}注：edges的元素可以设置为{v}思考：权值最小的边一定在最小生成树中么？分析:prim算法的时间复杂度？12语言代码参考C++模板//maxe保存了最大边数structedge{intu,v,w;booloperator(constedge&b)const{returnthis-wb.w;}}e[maxe];//并查集相关intf[maxn];inlinevoidinit(){for(inti=0;imaxn;i++)f[i]=i;}intfind(intx){if(f[x]==x)returnx;elsereturnf[x]=find(f[x]);}//主算法intkruskal(intn,intm){//n:点数,m:边数//所有边已经预先储存在e数组里sort(e,e+m);init();intans=0;for(inti=0;im;i++){intu=e[i].u,v=e[i].v,w=e[i].w;if(find(u)==find(v))continue;f[find(u)]=find(v);ans+=w;}returnans;}语言代码参考Prim算法-pascal语言varm,n:setof1..100;s,t,min,x,y,i,j,k,l,sum,p,ii:longint;a:array[1..100,1..100]oflongint;beginreadln(p);forii:=1topdobegink:=0;sum:=0;fillchar(a,sizeof(a),255);readln(x);m:=[1];n:=[2..x];fori:=1toxdobeginforj:=1toxdobeginread(a[i,j]);ifa[i,j]=0thena[i,j]:=maxlongint;end;readln;end;forl:=1tox-1dobeginmin:=maxlongint;fori:=1toxdoifiinmthenbeginforj:=1toxdobeginif(a[i,j]min)and(jinn)thenbeginmin:=a[i,j];s:=i;t:=j;end;end;end;sum:=sum+min;m:=m+[t];n:=n-[t];inc(k);end;writeln(sum);end;end.例题最短网络Agri-Net题目背景农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。题目描述约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000输入格式：第一行：农场的个数，N（3=N=100）。第二行..结尾:后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们限制在80个字符，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有线路从第i个农场到它本身。输出格式：只有一个输出，其中包含连接到每个农场的光纤的最小长度。例题最短网络Agri-Net输入输出样例输入样例#1：40492140817980162117160输出样例#1：28说明题目翻译来自NOCOW。USACOTrainingSection3.1例题最短网络Agri-Net参考程序constoo=maxlongint;vara:array[1..100,1..100]oflongint;//图（邻接矩阵）d:array[1..100]oflongint;//d[9]表示结点9到“已选集合”的距离。bo:array[1..100]ofboolean;//bo[9]=true就表示点9是已选集合的点，若bo[9]=false那么点9就不是已选集合的点了。n,i,j,k,p,min,sum:longint;beginreadln(n);fori:=1tondoforj:=1tondoread(a[i,j]);fillchar(bo,sizeof(bo),false);fori:=1tondod[i]:=oo;d[1]:=0;//一开始谁都不是已选集合的，点1到已选集合的距离为0，等下首先选1入已选集合sum:=0;fork:=1tondobegin//每次选一个到已选集合距离最小的点//第一步：选点(找那些还没有被找过，而且目前最小的点）min:=maxlongint;fori:=1tondoif(notbo[i])and(mind[i])then//选距离已选集合最小的点，前提是这个点它还没有加入已选集合beginmin:=d[i];//记录最小值p:=i;//记录点end;sum:=sum+d[p];//累加新的边//第二步：调整（调整那些没有被找过的点）bo[p]:=true;//f标记p已经是属于已选集合的了。以后不需要再选了。fori:=1tondo//这是调整！！p作为刚加入已选集合的点，需要做贡献的。if(notbo[i])and(d[i]a[p,i])thend[i]:=a[p,i];end;writeln(sum);end.18谢谢！