HYPERLINK"http://blog.csdn.net/pigli/article/details/5776587"最小生成树--普利姆(Prim)算法
分类：HYPERLINK"http://blog.csdn.net/pigli/article/category/712510"数据结构2010-07-3014:51593人阅读HYPERLINK"http://blog.csdn.net/pigli/article/details/5776587"\l"comments"评论(0)HYPERLINK"javascript:void(0);"\o"收藏"收藏HYPERLINK"http://blog.csdn.net/pigli/article/details/5776587"\l"report"\o"举报"举报
HYPERLINK"http://blog.csdn.net/tag/details.html?tag=%e7%ae%97%e6%b3%95"\t"_blank"算法HYPERLINK"http://blog.csdn.net/tag/details.html?tag=string"\t"_blank"stringHYPERLINK"http://blog.csdn.net/tag/details.html?tag=%e5%ad%98%e5%82%a8"\t"_blank"存储HYPERLINK"http://blog.csdn.net/tag/details.html?tag=%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84"\t"_blank"数据结构HYPERLINK"http://blog.csdn.net/tag/details.html?tag=class"\t"_blank"classHYPERLINK"http://blog.csdn.net/tag/details.html?tag=graph"\t"_blank"graph
最小生成树
1．为什么要构造最小生成树？什么是最小生成树？ 假设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。 在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。N个城市之间，最多可以设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢？在n个城市之间架设n-1条线路，使得这n个城市是连通的，这就是一个构造生成树的过程.在这n(n-1)/2中可能的方案中，选取总的耗费最小那一颗生成树，这就是最小生成树。2.?如何构造最小生成树？ 构造最小生成树的算法有普利姆(Prim)算法和克鲁斯卡(Kruskal)算法。这两个算法都是利用了最小生成树的性质：假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u属于U,v属于V-U，则必存在一颗包含边(u,v)的最小生成树。本文将实现普利姆(Prim)算法。那么首先来看看Prim算法实现的基本原理：假设N=(V,{E})是一个连通网，TE是N上最小生成树中边的集合。算法从U={u0}(u0属于V),TE={}开始，重复执行下述操作：在所有的u属于U,v属于V-U中的边(u,v)E中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则N=(V,{TE})为N的最小生成树。 思路决定出路。上面啰嗦这么多，只是为了从本质上认识最小生成树，以及最小生成树构造的原理。思路理清楚了，实现只不过是个过程而已，不会有迈步过去的砍。下面我们再更详细地描述下Prim算法。功夫不会负有心人的，磨刀也不会无砍柴工，相信我！思路理清楚了，程序写起来很快滴！^0^ 为了实现这个算法需附设一个辅助数组closedge，以记录从U到V-U具有最小代价的边。对每个顶点viV-U,在辅助数组中存在一个相应分量closedge[i-1]，它包括两个域：vex和lowcost。closedge[i-1].lowcost=Min{cost(u,vi)|uU}。vex域存储该边依附在U中的顶点。
具体算法描述：1．初始化closedge数组，用起始顶点到其它各结点权值初始化该数组。2．找出closegde数组中最小的权值的那个数组元素closedge[k]并将k并入到U中。这个并入的过程用将closegde[k].lowcost修改为0来标记。(V-U中各顶点到U中各顶点的权值最小的那个顶点。)3．将结点k到其它结点j(1<=j<=vetexnum)的权值arc[k][j]与数组closedge[j].lowcost进行比较。若arc[k][j]记住：closegde[j].lowcost中存储的是V-U中结点j到U中各结点的最小权值。
下面是算法实现：(思路清白了，程序实现20分钟就搞定^0^)
?
[java]HYPERLINK"http://blog.csdn.net/pigli/article/details/5776587"\o"viewplain"viewplainHYPERLINK"http://blog.csdn.net/pigli/article/details/5776587"\o"copy"copyHYPERLINK"http://blog.csdn.net/pigli/article/details/5776587"\o"print"printHYPERLINK"http://blog.csdn.net/pigli/article/details/5776587"\o"?"?
package?graph;??
public?class?MiniSpanTree_PRIM???
{??
????private?Closedge[]?closedge;???
????class?Closedge{??
????????String?vetex;??
????????int?lowcost;??
??????????
????????public?Closedge(String?vetex,int?lowcost)??
????????{??
????????????this.vetex?=?vetex;??
????????????this.lowcost?=?lowcost;??
????????}??
????}??
??????
????public?MiniSpanTree_PRIM(Graph_AdjMatrix?g,String?u)??//输入一个用领接矩阵表示的图和起始顶点??
????{??
????????int?k?=?g.getLocale(u);??
????????closedge?=?new?Closedge[g.vertex.length];??
????????for(int?i?=0;i????????{??
????????????if(i!=k){??
????????????????closedge[i]?=?new?Closedge(u,g.adjMatrix[k][i]);??
????????????}??
????????}??
????????closedge[k]?=?new?Closedge("",0);??
????????for(int?i?=1;i????????{??
????????????k?=?mininum(closedge);??
????????????System.out.println(closedge[k].vetex+","+g.vertex[k]);??
????????????closedge[k].lowcost?=?0;??
????????????for(int?j=0;j????????????{??
????????????????if(g.adjMatrix[k][j]????????????????{??
????????????????????closedge[j].vetex?=?g.vertex[k];??
????????????????????closedge[j].lowcost?=?g.adjMatrix[k][j];??
????????????????}??
????????????}??
????????}??
????}??
??????
????private?int?mininum(Closedge[]?array)??
????{??
????????int?weight?=array[0].lowcost;??
????????int?k=0;??
????????for(int?i=1;i????????{??
????????????if(array[i].lowcost==0)??
????????????????continue;??
????????????else??
????????????{??
????????????????if(weight==0)??
????????????????{??
????????????????????weight?=?array[i].lowcost;??
????????????????????k?=i;??
????????????????}??
????????????????else??
????????????????{??
????????????????????if(array[i].lowcost<=weight)??
????????????????????{??
????????????????????????weight?=?array[i].lowcost;??
????????????????????????k?=?i;??
????????????????????}??
????????????????}??
????????????}??
????????}??
????????return?k;??
????}??
}??
这只是一个表述Prim算法的类。若要是该算法为你构造最小生成树，那还需写一个驱动程序 |
|
