无向图的最小生成树（prim算法）

引子：

假设整个无向图中的点记为A，最小生成树中的点记为T，其他点记为Q（也就是Q= A-T），T与Q相连的边记为B

算法构造过程：

1、初始化：首先将一个点（随意一个）加入最小生成树中

2、在所有Q中找到一条与T中的某个点直接相连的并且权值最小的边B以及对应的点，加入最小生成树

3、重复以上过程，直到T=A。

 

</pre><pre name="code" class="java">package minTree;

import java.util.ArrayList;
import java.util.List;


public class MinTreeTest1 {

	public static void main(String[] args) {
		MinTree t = new MinTree(10);
		t.addVertex("v1");
		t.addVertex("v2");
		t.addVertex("v3");
		t.addVertex("v4");
		t.addVertex("v5");
		t.addVertex("v6");

		t.addEdge(0, 1, 6);
		t.addEdge(0, 2, 1);
		t.addEdge(0, 3, 5);
		t.addEdge(0, 4, 2000000);
		t.addEdge(0, 5, 2000000);

		t.addEdge(1, 2, 5);
		t.addEdge(1, 3, 2000000);
		t.addEdge(1, 4, 3);
		t.addEdge(1, 5, 2000000);

		t.addEdge(2, 3, 5);
		t.addEdge(2, 4, 6);
		t.addEdge(2, 5, 4);

		t.addEdge(3, 4, 2000000);
		t.addEdge(3, 5, 2);

		t.addEdge(4, 5, 6);

		t.printMatrix();

		int[][] a = t.buildMinTree2();
		
		 System.out.println();
		 int size = a.length;
		 for(int i = 0; i < size; i++){
			 for(int k = 0; k < size; k++){
				 System.out.print(a[i][k]+"; ");
			 }
			 System.out.println();
		 }
	}
}

class MinTree {

	private int[][] matrix = null;
	private Vertex[] vertexList = null;
	private int size = 0;
	private int maxSize = 20;

	
	public MinTree(int maxSize) {
		this.maxSize = maxSize;
		this.matrix = new int[maxSize][maxSize];
		this.vertexList = new Vertex[maxSize];
	}

	//增加顶点
	public void addVertex(String label) {
		if (isFull()) {
			throw new ArrayIndexOutOfBoundsException("满了！！");
		}
		vertexList[size] = new Vertex(label, -1);
		size++;
	}

	//增加边
	public void addEdge(int start, int end, int weigth) {
		if (start > size - 1 || end > size - 1) {
			throw new ArrayIndexOutOfBoundsException("没有这个元素");
		}

		if (start == end) {
			return;
		}

		this.matrix[start][end] = weigth;
		this.matrix[end][start] = weigth;
	}

	public boolean isFull() {
		return size == maxSize;
	}

	/**
	 * 顶点类
	 * @author LiangYH
	 *
	 */
	class Vertex {
		String label;
		int weigth;
		boolean isWired;

		public Vertex(String label, int weigth) {
			this.label = label;
			this.weigth = weigth;
			this.isWired = false;
		}

		public void printVertex() {
			System.out.println("label = " + label + "; weigth = " + weigth);
		}
	}

	//最大权值
	private static final int FLAG_WEIGTH = 10000;

	/**
	 * 生成最小生成树
	 * @return 最小生成树的邻接矩阵
	 */
	public int[][] buildMinTree2() {
		//存储最小生成树的邻接矩阵
		int [][] dyadic = new int[size][size];
		//存储最小生成树的顶点
		List<Integer> treeList = new ArrayList<>();
		//权值最小的点和边
		List<DoubleVertex> tempList = new ArrayList<>();
		//从第一个开始
		treeList.add(0);
		vertexList[0].isWired = true;
		//每次循环，最小生成树将增加一个顶点
		for (int j = 0; j < size; j++) {
			//找到将要加入最小生成树中的点和边
			int treeVertexIndex = -1;
			for (int i = 0; i < treeList.size(); i++) {
				treeVertexIndex = treeList.get(i);
				//每次循环，会找到最小生成树中的点到其他点权值最小的边以及对应的权重
				int tempWeigth = FLAG_WEIGTH;
				int indexFlag = -1;
				for (int k = 0; k < size; k++) {
					int tempWeigth2 = matrix[treeVertexIndex][k];
					if (tempWeigth2 > 0 && tempWeigth2 < tempWeigth&& !vertexList[k].isWired) {
						tempWeigth = tempWeigth2;
						indexFlag = k;
					}
				}
				if (tempWeigth != FLAG_WEIGTH) {
					DoubleVertex dou = new DoubleVertex(treeVertexIndex,indexFlag, tempWeigth);
					tempList.add(dou);
				}
			}
			//找到最小权值中的最小权值
			DoubleVertex tempDoubleVertex = new DoubleVertex(-1, -1,FLAG_WEIGTH);
			for (int i = 0; i < tempList.size(); i++) {
				if (tempList.get(i).weigth < tempDoubleVertex.weigth) {
					tempDoubleVertex = tempList.get(i);
				}
			}
			if (tempDoubleVertex.weigth != FLAG_WEIGTH) {
				//加入最小生成树
				treeList.add(tempDoubleVertex.outTreeIndex);
				//设置为已经连入最小生成树
				vertexList[tempDoubleVertex.outTreeIndex].isWired = true;
				//打印
				System.out.println(vertexList[tempDoubleVertex.inTreeIndex].label
								+ "; in Index = "+ tempDoubleVertex.inTreeIndex+
								"; "+ vertexList[tempDoubleVertex.outTreeIndex].label+
								"; out Index = "+ tempDoubleVertex.outTreeIndex + 
								"; weigth = "+ tempDoubleVertex.weigth);
				//维护最小生成树的邻接矩阵
				dyadic[tempDoubleVertex.inTreeIndex][tempDoubleVertex.outTreeIndex] = tempDoubleVertex.weigth;
				dyadic[tempDoubleVertex.outTreeIndex][tempDoubleVertex.inTreeIndex] = tempDoubleVertex.weigth;
				//清空
				tempList.clear();
			}
		}
		//还原
		for(int i = 0; i < size; i++){
			vertexList[i].isWired = false;
		}
		return dyadic;
	}

	//打印邻接矩阵
	public void printMatrix() {

		System.out.println();
		for (int i = 0; i < size; i++) {
			for (int k = 0; k < size; k++) {
				System.out.print(matrix[i][k] + "; ");
			}
			System.out.println();
		}
	}

	/**
	 * 记录两个顶点以及他们相连的权重
	 * @author admin
	 *
	 */
	class DoubleVertex {
		//最小生成树中的点
		int inTreeIndex;
		//非最小生成树中的点
		int outTreeIndex;
		//权重
		int weigth;

		public DoubleVertex(int inTreeIndex, int outTreeIndex, int weigth) {
			this.inTreeIndex = inTreeIndex;
			this.outTreeIndex = outTreeIndex;
			this.weigth = weigth;
		}

	}
}