普里姆算法是图结构中寻找最小生成树的一种算法-个人算法学习研究

gong

发布日期: 2020-08-21 10:27:45 浏览量: 86
评分:
star_border star_border star_border star_border star_border star_border star_border star_border star_border star_border
*转载请注明来自write-bug.com

/*

  • 普里姆算法是图结构中寻找最小生成树的一种算法。所谓生成树,即为连通图的极小连通子图,其包含了图中的n个顶点,
  • 和n-1条边,这n个顶点和n-1条边所构成的树即为生成树。当边上带有权值时,使生成树中的总权值最小的生成树称为最小代价生成树,简称最小生成树。最小生成树不唯一,且需要满足一下准则:

只能使用图中的边构造最小生成树
具有n个顶点和n-1条边
每个顶点仅能连接一次,即不能构成回路
获得图的最小生成树,即在保证图中所有顶点不重复连通的情况下,使得总权值最小。

如何使总权值最小
通过构造邻接矩阵找最小总权值,如图1右边所示。邻接矩阵中保存了顶点之间的连通关系和权值大小,我们可以构造最小代价数组lowcost[n]来记录图中与各顶点相连的最小权值(其中n为顶点数)。再构造顶点编号数组adjvex[],用于记录lowcost中权值所对应的顶点编号。初始化lowcost数组为邻接矩阵中第一行,即lowcost[] = {0,10,#,#,#,11,#,#,#} (这里用“#”表示图中无穷)。除去起始顶点v0外,其余为n-1条边的权值。我们将v1行的权值与lowcost数组中保存的权值对比,如果对应的权值比lowcost中的小,则替换之,这里比较后得到的lowcost[] = {0,10,18,#,#,11,16,#,12}。依次遍历邻接矩阵中剩余的v2到v8,即可得到总权值最小的lowcost数组。
但是,这样虽然保证了总权值最小,但是不能保证所有节点是连通的

由lowcost数组可以知道,权值为“#”是无效权值,即与当前顶点不相连的顶点,权值为0表示顶点本身或者说是已经匹配到的相连的最小权值点。在每次重建lowcost数组之后,遍历数组中的权值,将权值最小的项置为0,
表示对应顶点已经匹配到了权值最小的边。并记录该顶点的编号为minId,下次更新lowcost数组从minId开始搜寻,以此类推。比如,初始化lowcost后将权值最小的顶点,即v1置为0,得到lowcost[] = {0,0,#,#,#,11,#,#,#},minId = 1。之后,从v1开始替换lowcost中的权值。当lowcost中所有的权值都置为0时,即所有顶点都连通且保证总权值最小。

  • */

public class Prim {
public static void main(String[] args) {
int min = Integer.MAX_VALUE; //定义min变量保存每一个lowcost数组中的最小值,默认为无效权值
int minId = 0;//定义minId变量保存最小权值的顶点编号

上传的附件 cloud_download Prim.java ( 3.33kb, 0次下载 )
eject