/**
* 8.贪心算法_最小生成树_Kruskal(克鲁斯卡尔)算法
* @author Matt
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
public class Kruskal {
/**
* 创建一个Edge边类
* @author Matt
*/
public static class Edge implements Comparable<Edge> {
// 分别代表起始节点、终止节点、权值
int u, v, w;
// 构造器
public Edge(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
@Override
// 排序,按权值从小到大排序
public int compareTo(Edge o) {
int ow = o.w;
if (w < ow)
return -;
if (w == ow)
return ;
return ;
}
}
/**
* 克鲁斯卡尔算法
* @param V 序号
* @param E 边节点
*/
public static void Kruskal(int[] V, Edge[] E) {
Arrays.sort(E);// 将边按照权重w升序排序
// 创建一个ArrayList容器来保存所有边的表集合
ArrayList<HashSet> sets = new ArrayList<HashSet>();
// 从0到6进行遍历
for (int i = ; i < V.length; i++) {
// 创建一个哈希表
HashSet set = new HashSet();
// 从1开始设置边的序号,一共5个边
set.add(V[i]);
// 将表添加到容器中
sets.add(set);
}
// 遍历每一条边
for (int i = ; i < E.length; i++) {
// 取出每一个边节点的起始位置和终止位置
int start = E[i].u, end = E[i].v;
// 有些节点之间不同,赋为负值
int counti = -, countj = -;
// 从0到6遍历容器
for (int j = ; j < sets.size(); j++) {
// 取出容器中每一个边的表
HashSet set = sets.get(j);
// 如果存在数据,counti赋值为起始节点
if (set.contains(start)) {
counti = j;
}
// 如果存在数据,countj赋值为终止节点
if (set.contains(end)) {
countj = j;
}
}
// 若为负值则错误
if (counti < || countj < )
System.err.println("没有在子树中找到节点,错误");
// 起始节点和终止节点不为同一个
if (counti != countj) {
// 打印路径
System.out.println(
"start = " + start +
", end = " + end +
", weight = " + E[i].w);
// 从容器中取出序号为终止节点的边
HashSet setj = sets.get(countj);
sets.remove(countj); // 移除该边
// 从容器中取出序号为起始节点的边
HashSet seti = sets.get(counti);
sets.remove(counti); // 移除该边
// 设置起始节点为终止节点(进行两点连接)
seti.addAll(setj);
// 将该边添加至容器
sets.add(seti);
}
}
}
public static void main(String[] args) {
// 初始化
int[][] tree = {
{ -, , , , -, - },
{ , -, , -, , - },
{ , , -, , , },
{ , -, , -, -, },
{ -, , , -, -, },
{ -, -, , , , - } };
// 创建V和E数组
int[] V = { , , , , , };
Edge[] E = new Edge[];
E[] = new Edge(, , );
E[] = new Edge(, , );
E[] = new Edge(, , );
E[] = new Edge(, , );
E[] = new Edge(, , );
E[] = new Edge(, , );
E[] = new Edge(, , );
E[] = new Edge(, , );
E[] = new Edge(, , );
E[] = new Edge(, , );
Kruskal(V, E);
}
}
// 运行结果:
// start = 1, end = 3, weight = 1
// start = 4, end = 6, weight = 2
// start = 2, end = 5, weight = 3
// start = 3, end = 6, weight = 4
// start = 2, end = 3, weight = 5