引子：
假设整个无向图中的点记为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;}}}
