1 package iYou.neugle.graph;
2
3 import java.util.Set;
4 import java.util.TreeSet;
5
6 //创建图过程的代码在图的那篇博文中，此处直接使用
7 public class Kruskal {
8 private MyGraph1 graph;
9 private int[] a;// 并查集使用数组(存储前置节点)
10 private Set<Edge> edgeSet = new TreeSet<>();// 边的集合按w的升序排序
11
12 class Edge implements Comparable<Object> {
13 public int start;// 开始边
14 public int end;// 结束边
15 public int w;// 权值
16
17 // 将边的集合进行w的升序排序
18 @Override
19 public int compareTo(Object o) {
20 if (o instanceof Edge) {
21 Edge edge = (Edge) o;
22 if (this.w >= edge.w) {
23 return 1;
24 } else {
25 return -1;
26 }
27 }
28 return 0;
29 }
30 }
31
32 // 并查集
33 // 首先初始化各个节点
34 private void MakeSet(int n) {
35 for (int i = 0; i < n; i++) {
36 a[i] = i;
37 }
38 }
39
40 // 查找根节点
41 private int Find(int n) {
42 if (a[n] == n) {
43 return n;
44 } else {
45 return Find(a[n]);
46 }
47 }
48
49 // 合并节点
50 private void UnionSet(int x, int y) {
51 if (a[x] != a[y]) {
52 a[this.Find(y)] = this.Find(x);
53 }
54 }
55
56 public Kruskal(MyGraph1 graph) {
57 this.graph = graph;
58 a = new int[this.graph.getGraph().maxNum];
59 }
60
61 // 初始化edgeSet集合
62 private void Init() {
63 // 如果为无向图
64 if (this.graph.getGraph().type == 0) {
65 for (int i = 0; i < this.graph.getGraph().maxNum; i++) {
66 for (int j = 0; j < i; j++) {
67 Function(j, i);
68 }
69 }
70 }
71 // 如果为有向图
72 else {
73 for (int i = 0; i < this.graph.getGraph().maxNum; i++) {
74 for (int j = 0; j < this.graph.getGraph().maxNum; j++) {
75 Function(i, j);
76 }
77 }
78 }
79 }
80
81 // 功能函数
82 private void Function(int i, int j) {
83 int w = this.graph.getGraph().edge[i][j];
84 if (w != 0) {
85 Edge edge = new Edge();
86 edge.start = i;
87 edge.end = j;
88 edge.w = w;
89 this.edgeSet.add(edge);
90 }
91 }
92
93 public void KruskalCore() {
94 this.Init();
95 int maxNum = this.graph.getGraph().maxNum;
96 // 初始化a
97 this.MakeSet(maxNum);
98 Edge[] edgeArr = this.edgeSet.toArray(new Edge[] {});
99 int sum = edgeArr[0].w;
100 // 合并一条边的两个节点
101 this.UnionSet(edgeArr[0].start, edgeArr[0].end);
102 System.out.println("最小生成树为--------");
103 System.out
104 .println((edgeArr[0].start + 1) + "->" + (edgeArr[0].end + 1));
105 // 通过并查集进行判断是否该条边生成回路
106 int n = 1;
107 for (int i = 1; i < edgeArr.length && n < maxNum; i++) {
108 if (this.Find(edgeArr[i].start) != this.Find(edgeArr[i].end)) {
109 this.UnionSet(edgeArr[i].start, edgeArr[i].end);
110 System.out.println((edgeArr[i].start + 1) + "->"
111 + (edgeArr[i].end + 1));
112 sum += edgeArr[i].w;
113 }
114 n++;
115 }
116 System.out.println("----------------");
117 System.out.println("最小生成树的权值为: " + sum);
118 }
119
120 public static void main(String[] args) {
121 MyGraph1 graph = new MyGraph1(5, 0);
122 graph.CreateMaxtrixGraph(1, 2, 2);
123 graph.CreateMaxtrixGraph(1, 3, 5);
124 graph.CreateMaxtrixGraph(1, 5, 3);
125 graph.CreateMaxtrixGraph(2, 4, 4);
126 graph.CreateMaxtrixGraph(3, 5, 5);
127 graph.CreateMaxtrixGraph(4, 5, 2);
128 graph.OutPutMaxtrixGraph();
129 Kruskal kruskal = new Kruskal(graph);
130 kruskal.KruskalCore();
131 }
132 }
1 2 3 4 5
1 0 2 5 0 3
2 2 0 0 4 0
3 5 0 0 0 5
4 0 4 0 0 2
5 3 0 5 2 0
最小生成树为--------
1->2
4->5
1->5
1->3
----------------
最小生成树的权值为: 12
