无向图的最小生成树（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;
}

}
}