最小生成树的Prim算法和Kruskal算法--Java

65 阅读 0 评论 43 点赞

我是靠谱客的博主负责汽车，最近开发中收集的这篇文章主要介绍最小生成树的Prim算法和Kruskal算法--Java，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

最小生成树：

最小生成树是在无向图中，找到连通的树。该树由无向图中的N个节点构成，由N-1条边构成且不存在回路，且其总价值最低。最小生成树存在的必要条件是当且仅当G是连通的。

Prim算法：

prim算法是选择一步步的让这颗树长成。在每一步，都要把一个节点当做根并往上加边，这样也就把相关联的顶点给加入到树中。算法需要两个数组：lowestCost数组和cloest数组。需要两个顶点集：U和V。U集合表示已经加入到生成树的顶点，V表示还未加入到生成树的顶点。lowestCost数组表示从U中的节点到V中的节点做对应的最小值。比如lowestCost[i] = 3。就表示U集合中的顶点到顶点数组i这个位置代表的顶点的最短距离为3。cloest数组表示该顶点位置的前一个节点的位置，比如cloest[j] = 2就表示在顶点数组中j这个位置的顶点的前一个顶点的位置。因为cloest数组和顶点数组是相对应的。

该算法对于稠密图来说是比较有优势的。因为这是对顶点进行的操作。

算法流程：

先规定个其实节点i，将cloest中的全部位置都初始化为i。将lowestCost[i]的值初始化为0,0代表这个节点已经被加入到U中了。
接下来进行循环，找到U中的节点到V中的节点的最小值，更新lowestCost的值。在lowestCost的值中选择个最小的值的位置，然后把这个位置代表的节点加入到U中（也就是把对应的lowestCost的值更新为0）。再把对应的cloest的位置上的值修改为最小变的起点。
接下来就是重复2，直到所有的cloestCost的值都为0就代表所有的节点都已加入到U中。

无向图的创立和之前的dijkstra算法的创建的是一样的，依然使用邻接表进行存储的。

//最小生成树
	//prim算法，需要个lowestcost数组，表示U->V节点最短的权值
	int[] lowestCost;
	//需要个cloest数组，表示这个节点的前面的节点
	int[] cloest;
	public void prim() {
		lowestCost = new int[vertexNum.length];
		//先初始化为无穷大
		for(int i = 0;i<vertexNum.length;i++) {
			lowestCost[i] = Integer.MAX_VALUE;
		}
		cloest = new int[vertexNum.length];
		String  start = "1";
		int index = getIndex(start);
		vertex[index].visited = true;
		//让节点的开始节点都为这个开始节点
		for(int i = 0;i<cloest.length;i++) {
			cloest[i] = index;
		}
		//把开始节点的临近节点放入lowestCost数组中
		ArrayList<info> infor = vertex[index].adj;
		for(info t:infor) {
			lowestCost[t.index] = t.weight;
		}
		//lowestCost数组数值为0代表访问过
		lowestCost[index] = 0;
		
		//开始一个个的把节点加入到U中
		for(int i = 1;i<vertexNum.length;i++) {
			//首先获取第一个不为0的节点，为0说明已经以这个节点为根访问过
			for(int j = 0;j<vertexNum.length;j++) {
				if(lowestCost[j] != 0) {
					index = j;
					break;
				}
			}
			//找到值最小的节点
			
			for(int j = index;j<vertexNum.length;j++) {
				if(lowestCost[j]!=0 && lowestCost[j]<lowestCost[index]) {
					index = j;
				}
			}
			
			
			//这个位置信息的更改
			int flag = 0;
			for(int k = 0;k<vertexNum.length;k++) {
				if(lowestCost[k] == 0) {
					infor = vertex[k].adj;
					for(info t:infor) {
						if(t.index == index && t.weight == lowestCost[index]) {
							cloest[index] = k;
							flag = 1;
							break;
							
						}
					}
					if(flag == 1) {
						break;
					}
				}
			}
		
			lowestCost[index] = 0;
			
			infor = vertex[index].adj;
			for(info t:infor) {
				if(lowestCost[t.index]!=0 && t.weight < lowestCost[t.index]) {
					lowestCost[t.index] = t.weight;
				}
			}
		}
		
		
	}

Kruskal算法

Kruskal算法是基于连续的按照最小边的策略进行生成树的构建。Kruskal算法开始的时候把每个顶点都当做棵树，这样就是个森林，然后选取最小的边进行树的连接，最后生成只含有一棵树。该算法要遵循的有两点：

每次选取最小的边来构成生成树
将这条边加入后不能形成闭环

因此此时就得用到并查集的思想了。起初每个顶点都在自己的集合中，当加入一条边的时候就相当于把两个顶点放在了同一个集合里，当加入新边的时候，就要查询这个新边的顶点是不是已经属于一个集合了，如果已经属于一个集合了，此时就要舍弃掉这条边继续寻找新的最小边。如果不属于，就将这两个顶点放在一个新的集合里。所以，此时需要两个数组来进行操作算法：vtex数组用来判断两个顶点是不是属于同一个集合。E数组用来记录两个顶点之间的权值。算法过程为

首先在E数组里找到最小权值的边的两个顶点，记录下这两个顶点，并将这个数组对应的值置为0（0代表这条变已经被处理过了）
判断这两个顶点是不是属于一个集合，如果是就舍弃这这条边，如果不是就对这两个顶点进行Union操作
反复执行1,2操作，直到E数组里全部的值都为0。

该算法适合于边较少的情况。

代码：

//最小生成树  kruskal算法
	public void kruskal() {
		//需要E数组存储边的信息。
		int[][] E = new int[vertexNum.length][vertexNum.length];
		for(int i = 0;i<vertexNum.length;i++) {
			for (int j = 0; j < vertexNum.length; j++) {
				
					E[i][j] = Integer.MAX_VALUE;
				
			}
		}
		for(int i = 0;i<vertex.length;i++) {
			ArrayList<info> infor = vertex[i].adj;
			for(info t:infor) {
				E[i][t.index] = t.weight;
			}
		}
		
		//需要个节点数组进行是不是连接的判断
		
		int[] vtex = new int[vertexNum.length];
		for(int i = 0;i<vertexNum.length;i++) {
			vtex[i] = -1;
		}
		while(true) {
			int left = 0;
			int right = 0;
			for (int i = 0; i < vtex.length; i++) {
				for (int j = 0; j < vtex.length; j++) {
					if(E[i][j] != 0 && E[i][j] < E[left][right]) {
						left = i;
						right = j;
					}
				}
			}
			if(right == 0 && left == 0) {
				break;
			}
			E[left][right] = 0;
			E[right][left] = 0;
			
			if(getRoot(vtex,left) != getRoot(vtex,right)) {
				System.out.println("边："+vertex[left].number+"-> "+vertex[right].number);
				union(vtex,left,right);
			}
			
		}
		for(int i = 0;i<vertexNum.length;i++) {
			System.out.println(vtex[i]);
		}
		
	}
	
	private int getRoot(int[] vtex,int x) {
		if(vtex[x] == -1) {
			return x;
		}
		else
			return getRoot(vtex,vtex[x]);
	}
	
	private void union(int[] vtex,int left,int right) {
		right = getRoot(vtex,right);
		vtex[right] = left;
	}