【图算法】最小生成树之克鲁斯卡尔算法
最小生成树
在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。
克鲁斯卡尔算法(Kruskal)
克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
**基本思想：**按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
**具体做法：**首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。
算法分析
根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题：
问题一 对图的所有边按照权值大小进行排序。
问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。
问题一 很好解决，采用排序算法进行排序即可，在这里我用优先级队列，使其加入队列即有序。
问题二，处理方式是：记录顶点在"最小生成树"中的根结点，顶点的根结点是"在最小生成树中最先加入的顶点"。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的根结点是否重合，重合的话则会构成回路。 在这里我用并查集来实现（关于并查集请参考这里）。
在将(E,F) (C,D) (D,E)加入到最小生成树R中之后，这几条边的顶点就都有一个根结点：
- C的终点是E。
- F的终点是E。
因此，接下来，虽然(C,E)是权值最小的边。但是C和E的根结点点都是F，所以将(C,E)加入最小生成树的话，会形成回路。这就是判断回路的方式。
Java代码实现
边界路径类，主要记录了边的始末顶点，以及边的权值
class Edge{
public int srcVert;//边起始顶点的索引
public int destVert;//边终止顶点的索引
public int weight;//权重
public Edge(int sv, int dv, int w) {
srcVert = sv;
destVert = dv;
weight = w;
}
}
优先级队列
class PriorityQueue{
private final int SIZE = 20;
public Edge[] queArray;
private int size;
public PriorityQueue() {
queArray = new Edge[SIZE];
size = 0;
}
//有序的插入边
public void insert(Edge edge) {
int i;
//找到插入的位置
for(i = 0; i < size; i ++)
if(edge.weight >= queArray[i].weight )
break;
//插入位置后面的元素往后移一位，即权重比插入边小往后移一位
for(int j = size - 1; j >= i; j -- )
queArray[j + 1] = queArray[j];
//将edge插入腾出的位置
queArray[i] = edge;
size ++;
}
//删除权重最小的边
public Edge removeMin() {
return queArray[--size];
}
//删除n位置的边
public void removeN(int n) {
for(int i = n; i < size - 1; i ++)
queArray[i] = queArray[i + 1];
size --;
}
//返回权重最小的边
public Edge peekMin() {
return queArray[size - 1];
}
//返回n位置的边
public Edge peekN(int n) {
return queArray[n];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
//寻找特定的目的顶点的索引
public int find(int index) {
for(int i = 0; i < size; i ++)
if(queArray[i].destVert == index)
return i;
return -1;
}
public void display() {
if(size == 0)
return;
System.out.println("size:" + size);
for(int i = 0; i < size; i ++)
System.out.print(queArray[i].srcVert + " " + queArray[i].destVert + " -> ");
System.out.println();
}
}
有权图的最小生成树算法——克鲁斯卡尔算法
public class WeightGraph {
/**
* 存储结构为邻接矩阵
* @author Administrator
*
*/
class Vertex{//顶点类
public String data;
public boolean isVisted;
public boolean isInTree;
public Vertex(String data) {
this.data = data;
isVisted = false;
isInTree = false;
}
}
public final int MAX_VERTEX = 25;//顶点个数最大值
public final int MAX_VALUE = 65535;
public Vertex[] vertexArray;//顶点表
public int[][] edgeArray;//邻接矩阵
public int verNum;//顶点数量
public int curIndex;//当前顶点索引
public PriorityQueue pQueue;//存储边的优先级队列
public int nTree;//生成树中的顶点数量
//初始化图
public WeightGraph() {
vertexArray = new Vertex[MAX_VERTEX];
edgeArray = new int[MAX_VERTEX][MAX_VERTEX];
verNum = 0;
for(int i = 0; i < MAX_VERTEX; i ++)
for(int j = 0; j < MAX_VERTEX; j ++) {
if(i == j)
edgeArray[i][j] = 0;
else
edgeArray[i][j] = MAX_VALUE;
}
pQueue = new PriorityQueue();
}
//增加顶点
public void addVertex(String data) {
vertexArray[verNum ++] = new Vertex(data);
}
//增加边
public void addEdge(int start , int end, int weight) {
edgeArray[start - 1][end - 1] = weight;
edgeArray[end - 1][start - 1] = weight;
}
/**
* 克鲁斯卡尔算法
*/
public int minSpanninTreeKruskal() {
int result = 0;
UnionFind4 union = new UnionFind4(verNum );
for(int i = 0; i < verNum; i ++)
for(int j = i; j < verNum; j ++) {
if(edgeArray[i][j] != MAX_VALUE && edgeArray[i][j] != 0)
pQueue.insert(new Edge(i, j, edgeArray[i][j]));
}
while(nTree < verNum - 1) {
vertexArray[curIndex].isInTree = true;
Edge edge = pQueue.removeMin();
curIndex = edge.srcVert;
int end = edge.destVert;
if(union.isConnected(curIndex, end)) {
continue;
}
System.out.print(String.format("(%s,%s)",vertexArray[curIndex].data, vertexArray[end].data));
if(pQueue.size() != 0)
System.out.print("——>");
result += edge.weight;
union.union(curIndex, end);
nTree ++;
}
System.out.println();
return result;
}
并查集代码
package tree;
public class UnionFind4 implements UF{
private int[] parent;
private int[] rank;
public UnionFind4(int size) {
parent = new int[size];
rank = new int[size];
for(int i = 0 ; i < size ; i ++ ) {
parent[i] = i ;
rank[i] = 1;
}
}
public int getSize() {
return parent.length;
}
//查找元素p所对应的集合编号，时间复杂度为O（h）
int find(int p ) {
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("索引越界");
while( p != parent[p]) {
//路径压缩
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public boolean isConnected(int p , int q ) {
return find(p) == find(q);
}
//合并元素p和元素q所属集合,时间复杂度为O（h）
public void union(int p , int q) {
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot)
return;
if(rank[pRoot] < rank[qRoot])
parent[pRoot] = qRoot;
else if(rank[pRoot] > rank[qRoot])
parent[qRoot] = pRoot;
else {
parent[qRoot] = pRoot;
rank[pRoot] += 1;
}
}
}
测试代码
public static void main(String[] args) {
WeightGraph graph = new WeightGraph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");
graph.addVertex("G");
graph.addEdge(1, 2, 12);
graph.addEdge(1, 6, 16);
graph.addEdge(1, 7, 14);
graph.addEdge(2, 3, 10);
graph.addEdge(2, 6, 7);
graph.addEdge(3, 4, 3);
graph.addEdge(3, 5, 5);
graph.addEdge(3, 6, 6);
graph.addEdge(4, 5, 4);
graph.addEdge(5, 6, 2);
graph.addEdge(5, 7, 8);
System.out.println("最小生成树（克鲁斯卡尔算法）的权重之和：" + graph.minSpanninTreeKruskal());
//System.out.println("最小生成树（普利姆算法）的权重之和：" + graph.minSpanninTreePlim());
}
···
### 测试结果
