Java数据结构之普里姆算法（Prim算法）

- 日理万妓 2022-02-12 11:23 198阅读 0赞

# 介绍 #

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

1.  只能使用图中的边构造最小生成树
2.  具有n个顶点和n-1条边
3.  每个顶点仅能连接一次，即不能构成回路

# 核心思想 #

获得图的最小生成树，即在保证图中所有顶点不重复连通的情况下，使得总权值最小。

## 如何使总权值最小 ##

通过构造邻接矩阵找最小总权值，如图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数组。  
但是，这样虽然保证了总权值最小，但是不能保证所有节点是连通的。  
![该图仅用于分析][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70]

## 保证顶点连通 ##

由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变量保存最小权值的顶点编号
    		int sum = 0;//定义sum变量记录总权值
    		String[] Vertex = new String[] { "A", "B", "C", "D", "E", "F" };	//顶点集
    		int[][] Matrix = new int[6][];	//邻接矩阵
    		
    		//邻接矩阵初始化
    		Matrix[0] = new int[] { 0, 7, 5, 1, min, min };
    		Matrix[1] = new int[] { 7, 0, min, 6, 3, min };
    		Matrix[2] = new int[] { 5, min, 0, 7, min, 2 };
    		Matrix[3] = new int[] { 1, 6, 7, 0, 6, 4 };
    		Matrix[4] = new int[] { min, 3, min, 6, 0, 7 };
    		Matrix[5] = new int[] { min, min, 2, 4, 7, 0 };
    		
    		int vertexSize = Vertex.length;//顶点个数
    		int lowcost[]  = new int[vertexSize];//定义最小代价矩阵
    		int adjvex[] = new int[vertexSize];//定义数组保存最小权值的顶点编号
    		
    		//lowcost矩阵初始化
    		for(int i=0;i<vertexSize;i++) {
    			lowcost[i] = Matrix[0][i];
    		}
    		
    		for(int i=1;i<vertexSize;i++) {
    			min = Integer.MAX_VALUE;
    			minId = 0;
    			for(int j=1;j<vertexSize;j++) {
    				if(lowcost[j]!=0&&lowcost[j]<min) {//找到lowcost中的最小有效权值
    					min = lowcost[j];//记录最小值
    					minId = j;//记录最小权值的顶点编号
    				}
    			}
    			lowcost[minId] = 0;
    			sum += min;
    			System.out.println("连接顶点：" +Vertex[adjvex[minId]]+" 权值：" +min);
    			for(int j=1;j<vertexSize;j++) {
    				if(lowcost[j]!=0&&Matrix[minId][j]<lowcost[j]) {//在邻接矩阵中以编号为minId的顶点作为下一个顶点对lowcost中进行最小值替换
    					lowcost[j] = Matrix[minId][j];
    					adjvex[j] = minId;
    				}
    			}
    		}
    		
    		System.out.println("总权值为：" + sum);
    	}
    }

代码测试结果为：
    连接顶点：A 权值：1
    连接顶点：D 权值：4
    连接顶点：F 权值：2
    连接顶点：D 权值：6
    连接顶点：B 权值：3
    总权值为：16

上述为Prim算法的简易代码实现，可以将封装成类以方便调用。

package Prim;
    
    public class CloseEdge {
    	Object adjVex;
    	int lowCost;
    	public CloseEdge(Object adjVex, int lowCost) {
    		this.adjVex = adjVex;
    		this.lowCost = lowCost;
    	}
    }

package Prim;
    
    import cho6.MGraph;
    
    public class MiniSpanTree {
    	public Object[][] prim(MGraph g,Object u) throws Exception{
    		Object[][] tree = new Object[g.getVNum()-1][2];
    		int count=0;
    		CloseEdge[] closeEdge = new CloseEdge[g.getVNum()];//用于保存最小代价和对应的顶点
    		int k = g.locateVex(u);//起始顶点的位置
    		for(int j=0;j<g.getVNum();j++) {
    			if(j!=k)
    				closeEdge[j] = new CloseEdge(u,g.getArcs(k, j));//初始化，即保存邻接矩阵起始顶点所在行的权值
    		}
    		closeEdge[k] = new CloseEdge(u, 0);//将起始顶点对应的权值置为0
    		for(int i=1;i<g.getVNum();i++) {
    			k = getMinMum(closeEdge);
    			tree[count][0] = closeEdge[k].adjVex;
    			tree[count][1] = g.getVex(k);
    			count++;
    			closeEdge[k].lowCost = 0;
    			for(int j=0;j<g.getVNum();j++) {
    				if(g.getArcs(k, j)<closeEdge[j].lowCost)
    					closeEdge[j] = new CloseEdge(g.getVex(k),g.getArcs(k, j));
    			}
    		}
    		
    		return tree;
    	}
    	
    	private int getMinMum(CloseEdge[] closeEdge) {
    		int min = Integer.MAX_VALUE;
    		int v = -1;
    		for(int i=0;i<closeEdge.length;i++) {
    			if(closeEdge[i].lowCost!=0&&closeEdge[i].lowCost<min) {
    				min = closeEdge[i].lowCost;
    				v = i;
    			}
    		}
    		
    		return v;
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70]: /images/20220212/f708c2854baf4661ae13a6c983c41930.png