踉踉跄跄写出来了,原理我基本懂了,但是感觉有点讲不出来,这里只贴一下代码:
package cn.nrsc.graph;
/**
*
* @author 孙川 最小生成树-克鲁斯卡尔算法
*
*/
public class Graph_Kruskal {
// ------ 边实体----------
class Edge {
private int begin;
private int end;
private int weight;
public Edge(int begin, int end, int weight) {
this.begin = begin;
this.end = end;
this.weight = weight;
}
}
// ------ 边实体----------
private Edge[] edges; // 边数组
private int edgeSize; // 边的数量
public Graph_Kruskal(int edgeSize) {
this.edgeSize = edgeSize;
this.edges = new Edge[edgeSize];
}
// 生成边数组
public void createEdges() {
edges[0] = new Edge(4, 7, 7);
edges[1] = new Edge(2, 8, 8);
edges[2] = new Edge(0, 1, 10);
edges[3] = new Edge(0, 5, 11);
edges[4] = new Edge(1, 8, 12);
edges[5] = new Edge(3, 7, 16);
edges[6] = new Edge(1, 6, 16);
edges[7] = new Edge(5, 6, 17);
edges[8] = new Edge(1, 2, 18);
edges[9] = new Edge(6, 7, 19);
edges[10] = new Edge(3, 4, 20);
edges[11] = new Edge(3, 8, 21);
edges[12] = new Edge(2, 3, 22);
edges[13] = new Edge(3, 6, 24);
edges[14] = new Edge(4, 5, 26);
}
// 克鲁斯卡尔算法
public void Kruskal() {
// 初始化"回环判断"数组
int[] fromTo = new int[edgeSize];
int sum = 0;
// 从权重最小的边开始,如果没有形成回环,则该边是满足条件的边
for (int i = 0; i < edgeSize; i++) {
int n = find(fromTo, edges[i].begin);
int m = find(fromTo, edges[i].end);
if (n != m) {
fromTo[n] = m;
System.out.println();
System.out.println("起始顶点:" + edges[i].begin + "---->结束顶点:" + edges[i].end);
sum += edges[i].weight;
} else {
System.out.println("第" + i + "条边出现了回环");
}
}
System.out.println("最小生成树的总距离为:" + sum);
}
private int find(int[] p, int f) {
System.out.print("|||***> " + f);
while (p[f] > 0) {
f = p[f];
System.out.print("----> " + f);
}
return f;
}
public static void main(String[] args) {
Graph_Kruskal graph = new Graph_Kruskal(15);
graph.createEdges();
graph.Kruskal();
}
}
运行结果也贴一下:
