kruskal算法java
时间: 2023-11-04 20:57:14 浏览: 42
Kruskal算法是一种构造最小生成树的算法,适用于边稀疏而顶点较多的图。其核心原理是通过不断选择边权值最小且不构成环的边来构建最小生成树。在Kruskal算法中,我们需要使用并查集数据结构来判断两个顶点是否属于同一棵树,以避免形成环。具体实现时,可以使用优先队列(PriorityQueue)来按照边的权值进行排序,并查集来判断是否属于同一棵树。
下面是一个示例的Kruskal算法的Java实现:
```java
import java.util.*;
class Edge implements Comparable<Edge> {
int src, dest, weight;
public int compareTo(Edge other) {
return this.weight - other.weight;
}
}
class KruskalAlgorithm {
int V, E;
Edge[] edges;
KruskalAlgorithm(int V, int E) {
this.V = V;
this.E = E;
edges = new Edge[E];
for (int i = 0; i < E; i++) {
edges[i] = new Edge();
}
}
int find(int[] parent, int i) {
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
void union(int[] parent, int x, int y) {
int xRoot = find(parent, x);
int yRoot = find(parent, y);
parent[xRoot] = yRoot;
}
void kruskalMST() {
Edge[] result = new Edge[V];
int[] parent = new int[V];
for (int i = 0; i < V; i++) {
parent[i] = -1;
}
Arrays.sort(edges);
int e = 0;
int i = 0;
while (e < V - 1 && i < E) {
Edge nextEdge = edges[i++];
int x = find(parent, nextEdge.src);
int y = find(parent, nextEdge.dest);
if (x != y) {
result[e++] = nextEdge;
union(parent, x, y);
}
}
System.out.println("Kruskal's Minimum Spanning Tree:"); for (i = 0; i < e; i++) {
System.out.println(result[i].src + " -- " + result[i].dest + " with weight " + result[i].weight);
}
}
}
public class Main {
public static void main(String[] args) {
int V = 4; // 顶点数
int E = 5; // 边数
KruskalAlgorithm graph = new KruskalAlgorithm(V, E);
// 添加边的信息
graph.edges[0].src = 0;
graph.edges[0].dest = 1;
graph.edges[0].weight = 10;
graph.edges[1].src = 0;
graph.edges[1].dest = 2;
graph.edges[1].weight = 6;
graph.edges[2].src = 0;
graph.edges[2].dest = 3;
graph.edges[2].weight = 5;
graph.edges[3].src = 1;
graph.edges[3].dest = 3;
graph.edges[3].weight = 15;
graph.edges[4].src = 2;
graph.edges[4].dest = 3;
graph.edges[4].weight = 4;
graph.kruskalMST();
}
}
```