最小生成树(自己理解的,不当之处希望有人可以指出)

简单的说一下最小生成树:

假设一个图,它有n个顶点,则只需n-1条边,就可以将其组成一个连通图,在各种组合中,所有n-1条边的权重之和最小的连通图,就是所谓的最小生成树.

 

算法思想(自己揣摩的,不当之处希望有人可以指出)

如上图,我们以v0为起点对整个图求其最小生成树,过程如下:

首先既然以v0开始,那么v0肯定就加入到了最小生成树中,然后计算v0距离其他各个顶点的距离.不连通的以无穷大表示,则得到vo距离其他各个顶点距离如下:

这代表什么意思呢?

其实很简单,就是与v0相连通的点只有v1和v11,而最小生成树要求v0必须要与图中其他n-1个中的某一个点进行连通,且权重值最小,因此很自然而然的我们会让v0和v1连接起来

 

按照普里姆算法的思想既然V0和v1这条边已经确定了,且v0与其他各个顶点的权重值也知道了,我们这个时候可以继续考虑一下v1的连通情况及其权重大小 ,同时由于v0和v1已经确定了,我们就先不管他们了,将其值可以都设为0,则:

 

 

上图中得到的这个数组表示什么意思呢?其实很好理解,就是v0和v1两个顶点与其它各个顶点的连通性与权重.

那这个东东有什么用呢?这时候我们就要有一个整体的思想,为了保证连通性以及权重最小,vo和v1两个已经确定了的点肯定要与其它的点进行连接,而上面的数组列出了所有与v0以及v1相连通的点,只要选最小的那个,我们就找到了答案.

重复上面两个步骤,就得到了满足要求的最小生成树.

package cn.nrsc.graph;

public class Graph_Prim {
	// ----------------------------图的表示方式------------------------
	private int vertexSize;// 顶点的数量
	private int[] vertexs;// 顶点对应的数组
	private int[][] matrix;// 邻接矩阵
	private static final int MAX_WEIGHT = 1000;// 代表顶点之间不连通
	private boolean[] isVisited; // 顶点是否已经被访问

	public Graph_Prim(int vertexSize) {
		this.vertexSize = vertexSize;
		this.matrix = new int[vertexSize][vertexSize];
		this.vertexs = new int[vertexSize];
		for (int i = 0; i < vertexSize; i++) {
			vertexs[i] = i;
		}

		isVisited = new boolean[vertexSize];
	}
	// ----------------------------图的表示方式------------------------

	// 最小生成树----普里姆算法
	public void prim() {
		// 假设最先取出顶点0,并遍历出它与其他所有顶点的距离----正好就是图中邻接矩阵的第一行
		int[] distance = matrix[0];

		int sum = 0; // 总距离

		System.out.print("查找到点的顺序:0");

		// 控制向树中添加点的次数
		// 因为默认取出了一个点加入到了最小生成树中,则还需要再确定另外n-1个点的加入顺序
		for (int i = 1; i < vertexSize; i++) {
			// 假设初始最小值如下:
			int min = MAX_WEIGHT;
			int minId = 0;

			// 遍历距离数组找出该数组中除了距离为0(说明该点已经加入到了最小生成树中)和距离为无穷大的
			// 所有顶点中距离最小的那个----说明这个点是与已经确定的所有点可以连通,而且值最小
			for (int j = 1; j < vertexSize; j++) {
				if (distance[j] > 0 && distance[j] < MAX_WEIGHT && distance[j] < min) {
					min = distance[j];
					minId = j;
				}
			}

			// 将minId标定为已经确定的点
			distance[minId] = 0;

			System.out.print("--->" + minId);
			// 计算总距离
			sum += min;

			// 遍历minId点的所有邻接点,找到已确定点到其他未知点之间更小的距离
			// 0肯定不用再遍历了,因为第一个确定的点就是它,所以从1开始
			for (int k = 1; k < vertexSize; k++) {
				if (distance[k] > 0 && distance[k] > matrix[minId][k]) {
					distance[k] = matrix[minId][k];
				}
			}
		}
		System.out.println();
		System.out.println("最小生成树的总距离为:" + sum);

	}
	// 最小生成树----普里姆算法

	public static void main(String[] args) {
		Graph_Prim graph = new Graph_Prim(9);
		int[] v0 = { 0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT };
		int[] v1 = { 10, 0, 18, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, MAX_WEIGHT, 12 };
		int[] v2 = { MAX_WEIGHT, MAX_WEIGHT, 0, 22, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8 };
		int[] v3 = { MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, 24, 16, 21 };
		int[] v4 = { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 20, 0, 26, MAX_WEIGHT, 7, MAX_WEIGHT };
		int[] v5 = { 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 26, 0, 17, MAX_WEIGHT, MAX_WEIGHT };
		int[] v6 = { MAX_WEIGHT, 16, MAX_WEIGHT, 24, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT };
		int[] v7 = { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, 7, MAX_WEIGHT, 19, 0, MAX_WEIGHT };
		int[] v8 = { MAX_WEIGHT, 12, 8, 21, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0 };

		graph.matrix[0] = v0;
		graph.matrix[1] = v1;
		graph.matrix[2] = v2;
		graph.matrix[3] = v3;
		graph.matrix[4] = v4;
		graph.matrix[5] = v5;
		graph.matrix[6] = v6;
		graph.matrix[7] = v7;
		graph.matrix[8] = v8;
		
		//test
		graph.prim();

	}
}