使用 Java Stream API 实现最小生成树的 Kruskal克鲁斯卡尔 算法
Kruskal 算法是一种流行的方法，用于查找连通无向图的最小生成树 (MST)。该算法的工作原理是按权重升序选择边，同时确保将边添加到 MST 不会创建循环。在这篇博文中，我们将探讨如何使用 Java Stream API 实现 Kruskal 算法。
什么是克鲁斯卡尔Kruskal 算法
在深入实现之前，我们先简要讨论一下 Kruskal 算法所涉及的步骤：
- 1. 对边进行排序：将图中的所有边按照其权重非降序进行排序。
- 2.初始化MST：创建一个空集来存储MST的边。
- 3. 迭代边：按排序顺序迭代所有边。对于每条边：
- - 如果将边添加到 MST 不会创建环路，则将其添加到 MST。
- - 否则，丢弃边缘。
- 4.输出MST：添加到MST的边集合形成最小生成树。
使用Java Stream API实现
要使用Java Stream API实现Kruskal算法，我们需要遵循以下步骤：
- 1. 定义一个类来表示图中的一条边，包括源、目的地和权重。
- 2. 创建一种根据权重对边进行排序的方法。
- 3. 实现一种方法来查找不相交集合中顶点的父级。
- 4. 使用Java Stream API 实现主要算法。
让我们从定义 Edge 类开始：
class Edge {
int source, destination, weight;
public Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}
|
接下来，我们创建一个方法来根据边的权重对边进行排序：
private static List<Edge> sortEdges(List<Edge> edges) {
return edges.stream()
.sorted(Comparator.comparingInt(e -> e.weight))
.collect(Collectors.toList());
}
|
现在，我们需要实现一种方法来查找不相交集合中顶点的父级。此方法对于检测图中的循环至关重要：
private static int findParent(int[] parent, int vertex) {
if (parent[vertex] == -1)
return vertex;
return findParent(parent, parent[vertex]);
}
|
最后，我们可以使用Java Stream API来实现主要算法：
public static List<Edge> kruskalMST(List<Edge> edges, int vertices) {
List<Edge> result = new ArrayList<>();
List<Edge> sortedEdges = sortEdges(edges);
int[] parent = new int[vertices];
Arrays.fill(parent, -1);
sortedEdges.stream().forEach(edge -> {
int x = findParent(parent, edge.source);
int y = findParent(parent, edge.destination);
if (x != y) {
result.add(edge);
parent[x] = y;
}
});
return result;
}
|
使用示例
以下是如何使用 kruskalMST 方法查找图的最小生成树的示例：
public static void main(String[] args) {
List<Edge> edges = Arrays.asList(
new Edge(0, 1, 10),
new Edge(0, 2, 6),
new Edge(0, 3, 5),
new Edge(1, 3, 15),
new Edge(2, 3, 4)
);
List<Edge> mst = kruskalMST(edges, 4);
System.out.println("Minimum Spanning Tree:");
mst.forEach(edge -> System.out.println(edge.source + " - " + edge.destination + ": " + edge.weight));
}
|
结论
在这篇博文中，我们讨论了如何使用 Java Stream API 实现 Kruskal 算法来查找图的最小生成树。 Java Stream API 提供了一种简洁且可读的方式来处理集合，使其成为实现 Kruskal 算法等算法的合适选择。