- 技术博客
- 最小生成树 Kruskal算法实现
import java
.util
.Arrays
;
import java
.util
.Comparator
;
import java
.util
.Scanner
;
public class Kruskal {
private static int numberOfVertics
;
private static int numberOfEdges
;
private static int[] parent
;
private static int[] rank
;
private static Edge
[] edgeSet
;
public static void main(String
[] args
) {
init();
int count
= 0;
Edge edge
;
System
.out
.println("\nstart");
for (int i
= 0; i
< numberOfEdges
; i
++) {
edge
= edgeSet
[i
];
if (find(edge
.start
) != find(edge
.end
)) {
union(edge
.start
, edge
.end
);
count
++;
System
.out
.println(edge
.start
+ "---" + edge
.end
+ " 权：" + edge
.weigth
);
if (count
== numberOfVertics
- 1) {
System
.out
.println("over");
System
.out
.println("由这些边组成的图是否连通（连通即为树）"+ isConnected());
return;
}
}
}
}
private static boolean isConnected() {
int root
= find(1);
for(int i
= 2; i
< numberOfVertics
+ 1; i
++) {
if(find(i
) != root
) {
return false;
}
}
return true;
}
private static void init() {
Scanner scanner
= new Scanner(System
.in
);
System
.out
.println("输入顶点数：");
numberOfVertics
= scanner
.nextInt();
System
.out
.println("输入边数：");
numberOfEdges
= scanner
.nextInt();
parent
= new int[numberOfVertics
+ 1];
rank
= new int[numberOfVertics
+ 1];
edgeSet
= new Edge[numberOfEdges
];
for (int i
= 1; i
< numberOfVertics
+ 1; i
++) {
parent
[i
] = i
;
}
System
.out
.println("输入边顶点及权（ 格式：顶点a 顶点b 权值）");
for (int i
= 0; i
< numberOfEdges
; i
++) {
Edge edge
= new Edge();
edge
.start
= scanner
.nextInt();
edge
.end
= scanner
.nextInt();
edge
.weigth
= scanner
.nextDouble();
if(edge
.start
> numberOfVertics
|| edge
.end
> numberOfEdges
) {
throw new ArrayIndexOutOfBoundsException();
}
edgeSet
[i
] = edge
;
}
scanner
.close();
Arrays
.sort(edgeSet
, new Comparator<Edge>() {
@Override
public int compare(Edge e1
, Edge e2
) {
if (e1
.weigth
> e2
.weigth
) {
return 1;
}
return -1;
}
});
}
private static int find(int v
) {
if (parent
[v
] == v
) {
return v
;
}
return parent
[v
] = find(parent
[v
]);
}
private static void union(int v1
, int v2
) {
int root1
= find(v1
);
int root2
= find(v2
);
if (root1
== root2
) {
return;
}
if (rank
[root1
] > rank
[root2
]) {
parent
[root2
] = root1
;
} else if (rank
[root1
] < rank
[root2
]) {
parent
[root1
] = root2
;
} else {
parent
[root1
] = root2
;
rank
[root2
] += 1;
}
}
private static class Edge {
int start
;
int end
;
double weigth
;
}
}
