最小生成树的算法――减枝算法.doc

最小生成树的算法――减枝算法.doc最小生成树的算法――减枝算法摘要:最小生成树是数据结构中图的一种重要应用,对于具有n个顶点的带权连通图可以建立许多不同的生成树。Kruskal算法和Prim算法是求最小生成树的常用算法。本文讨论了一种新的算法。关键词:最小生成树;pirm算法;kruskal算法中图分类号::A文章编号:1007-9599(2011)09-0000-01 MinimumSpanningTreeAlgorithm-BranchCutAlgorithm LiuXin (SchoolofInformationResourceManagement,RenminUniversityofChina,Beijing100872,China) Abstract:Minimumspanningtreedatastructureisanimportantapplicationin,. Keywords:Minimumspanningtree;PirmalgorithmKruskalalgorithm; 一、引言在现实社会中,常常会遇到有关于n个城市之间建立通信联络网,不同城市间建立的代价各不相同。N个小区需要铺设管道,不同小区之间的代价也不同。这样,我们自然会考虑这样一个问题,怎么样在最节省的情况下(代价最小)建立一个是所有不同点都联通的网络。实践中应用于线路、管道辅设、运输问题设备更新决策等。现在,我们考虑的就是怎么样找到一颗生成树,使得总的耗费最少。最小生成树的构造准则: ;-1条边来连接网络中的n个顶点;。最小生成树问题的解法主要有三种:Prim算法,Kruskal算法和“破圈”算法。 Prim和kruskal这两种算法是按权值递增的顺序构造连通网的最小生成树. 二、算法实现的思路现在最常使用的prim算法和kruskal算法的基本思路均为避圈法,均为一种贪心算法。 Prim算法是利用MST性质找到最初的连通图,并一步步找到使不在连通图中的点与连通图连接而代价最小的边,因对于每一个点来说,只会将它与连通图连接一次,所以prim算法会保证生成树不会成环。 Kruskal算法则是直接利用了避圈的思路,每一次找到不使图构成环的代价最小的边,根据MST性质我们易知找到的第一条边就是图中代价最小的边。之后每次找到代价最小而不会构成环的边,在将所有点连通时停止,即得到最小生成树本文主要论述的是在考虑图中所有点和所有有权的边时,尽量“贪心”的删除权较大的边,并保证图是联通的。一直剪至n-1条边时,不能继续剪枝。三、算法过程(一)算法中用到的变量。[n][n]为带权无向图的邻接矩阵,其中若Vi与Vj之间有边且权为w,则a[i][j]=w,否则a[i][j]=0。[n][4]是所有边按照权值由大到小排序的数组,其中包括边的权值,边的位置p,q,变量p,若找到的要删去的边是Vi与Vj之间的边,则将a[i][j]和a[j][i]置为0,表示这两点之间的边已