kruskal求最小生成树java
时间: 2024-04-21 09:18:25 浏览: 11
以下是Kruskal算法求最小生成树的Java实现:
```java
package com.zhiyiyo.graph;
import java.util.ArrayList;import java.util.Collections;
import java.util.List;
/**
* Kruskal算法求最小生成树
*/
public class KruskalMST implements MST {
private List<Edge> mst; // 最小生成树的边
private double weight; // 最小生成树的权重
public KruskalMST(EdgeWeightedGraph G) {
mst = new ArrayList<>();
List<Edge> edges = new ArrayList<>();
for (Edge e : G.edges()) {
edges.add(e);
}
Collections.sort(edges); // 将边按照权重从小到大排序
UF uf = new UF(G.V()); // 并查集,用于判断两个顶点是否连通
for (Edge e : edges) {
int v = e.either(), w = e.other(v);
if (!uf.connected(v, w)) { // 如果两个顶点不连通,则将这条边加入最小生成树中
uf.union(v, w);
mst.add(e);
weight += e.weight();
}
}
}
@Override
public Iterable<Edge> edges() {
return mst;
}
@Override
public double weight() {
return weight;
}
}
```
使用方法如下:
```java
EdgeWeightedGraph G = new EdgeWeightedGraph(V);
// 添加边
KruskalMST mst = new KruskalMST(G);
for (Edge e : mst.edges()) {
System.out.println(e);
}
System.out.println(mst.weight());
```