kruskal算法 java
时间: 2023-11-10 13:03:13 浏览: 48
Kruskal算法是一种用于求解最小生成树的贪心算法。它的基本思想是将所有边按照权值从小到大排序,然后依次加入到生成树中,如果加入该边不会形成环,则将该边加入生成树中。
以下是Kruskal算法的Java实现:
```java
import java.util.*;
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;
}
public int compareTo(Edge e) {
return this.w - e.w;
}
}
class Kruskal {
int[] parent;
int[] rank;
public Kruskal(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int px = find(x);
int py = find(y);
if (px == py) {
return;
}
if (rank[px] > rank[py]) {
parent[py] = px;
} else if (rank[px] < rank[py]) {
parent[px] = py;
} else {
parent[py] = px;
rank[px]++;
}
}
public int kruskal(Edge[] edges) {
Arrays.sort(edges);
int n = parent.length;
int res = 0;
for (Edge e : edges) {
if (find(e.u) != find(e.v)) {
union(e.u, e.v);
res += e.w;
}
}
return res;
}
}
public class Main {
public static void main(String[] args) {
int n = 5;
Edge[] edges = new Edge[7];
edges[0] = new Edge(0, 1, 2);
edges[1] = new Edge(0, 2, 3);
edges[2] = new Edge(1, 2, 4);
edges[3] = new Edge(1, 3, 1);
edges[4] = new Edge(2, 3, 5);
edges[5] = new Edge(2, 4, 4);
edges[6] = new Edge(3, 4, 6);
Kruskal kruskal = new Kruskal(n);
int res = kruskal.kruskal(edges);
System.out.println(res); // 输出最小生成树的权值和
}
}
```