Java Stream API：实现 Kruskal 算法

使用 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 算法等算法的合适选择。