Class MinimumSpanningTreeUtil

java.lang.Object
cloud.opencode.base.graph.algorithm.MinimumSpanningTreeUtil
public final class MinimumSpanningTreeUtil extends Object
Minimum Spanning Tree Util 最小生成树工具类

Utility class for minimum spanning tree algorithms.

最小生成树算法的工具类。

Algorithms | 算法:

  • Prim - O((V+E)logV) with priority queue | 使用优先队列 O((V+E)logV)
  • Kruskal - O(ElogE) with union-find | 使用并查集 O(ElogE)

Features | 主要功能:

  • Prim's algorithm with priority queue - 使用优先队列的Prim算法
  • Kruskal's algorithm with union-find - 使用并查集的Kruskal算法
  • MST total weight calculation - 最小生成树总权重计算

Usage Examples | 使用示例:

// Get MST using Prim's algorithm
Set<Edge<String>> mstPrim = MinimumSpanningTreeUtil.prim(graph, "A");

// Get MST using Kruskal's algorithm
Set<Edge<String>> mstKruskal = MinimumSpanningTreeUtil.kruskal(graph);

// Get total weight
double weight = MinimumSpanningTreeUtil.mstWeight(graph);

Security | 安全性:

  • Thread-safe: Yes (stateless utility class) - 线程安全: 是（无状态工具类）
  • Null-safe: Yes (returns empty results for null inputs) - 空值安全: 是（null输入返回空结果）

Performance | 性能特性:

  • Time complexity: O(E log E) - 时间复杂度: O(E log E)
  • Space complexity: O(V + E) - 空间复杂度: O(V + E)
Since:
JDK 25, opencode-base-graph V1.0.0
Author:
Leon Soo www.LeonSoo.com
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    MinimumSpanningTreeUtil.UnionFind<V>
    Union-Find (Disjoint Set Union) data structure 并查集数据结构

  • Method Summary

    Modifier and Type
    Method
    Description
    static <V> int
    componentCount(Graph<V> graph)
    Get the count of connected components after MST/MSF construction 获取MST/MSF构建后的连通分量数
    static <V> boolean
    hasSpanningTree(Graph<V> graph)
    Check if a graph has a spanning tree (is connected) 检查图是否有生成树（是否连通）
    static <V> Set<Edge<V>>
    kruskal(Graph<V> graph)
    Find minimum spanning tree using Kruskal's algorithm 使用Kruskal算法查找最小生成树
    static <V> Set<Edge<V>>
    minimumSpanningForest(Graph<V> graph)
    Find minimum spanning forest for disconnected graph 为不连通图查找最小生成森林
    static <V> double
    mstWeight(Graph<V> graph)
    Calculate the total weight of the minimum spanning tree 计算最小生成树的总权重
    static <V> Set<Edge<V>>
    prim(Graph<V> graph)
    Find minimum spanning tree using Prim's algorithm (auto-select start) 使用Prim算法查找最小生成树（自动选择起点）
    static <V> Set<Edge<V>>
    prim(Graph<V> graph, V start)
    Find minimum spanning tree using Prim's algorithm 使用Prim算法查找最小生成树
    static <V> double
    totalWeight(Set<Edge<V>> edges)
    Calculate the total weight of a set of edges 计算边集合的总权重

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • prim

      public static <V> Set<Edge<V>> prim(Graph<V> graph, V start)
      Find minimum spanning tree using Prim's algorithm 使用Prim算法查找最小生成树

      Starts from the given vertex and greedily adds the minimum weight edge that connects a vertex in the tree to a vertex outside the tree.

      从给定顶点开始，贪婪地添加连接树内顶点和树外顶点的最小权重边。

      Time Complexity | 时间复杂度: O((V+E)logV)

      Space Complexity | 空间复杂度: O(V+E)

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the undirected graph | 无向图
      start - the starting vertex | 起始顶点
      Returns:
      set of edges in the MST | 最小生成树的边集合

    • prim

      public static <V> Set<Edge<V>> prim(Graph<V> graph)
      Find minimum spanning tree using Prim's algorithm (auto-select start) 使用Prim算法查找最小生成树（自动选择起点）
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the undirected graph | 无向图
      Returns:
      set of edges in the MST | 最小生成树的边集合

    • kruskal

      public static <V> Set<Edge<V>> kruskal(Graph<V> graph)
      Find minimum spanning tree using Kruskal's algorithm 使用Kruskal算法查找最小生成树

      Sorts all edges by weight and greedily adds edges that don't create a cycle.

      按权重排序所有边，贪婪地添加不会创建环的边。

      Time Complexity | 时间复杂度: O(ElogE)

      Space Complexity | 空间复杂度: O(V)

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the undirected graph | 无向图
      Returns:
      set of edges in the MST | 最小生成树的边集合

    • mstWeight

      public static <V> double mstWeight(Graph<V> graph)
      Calculate the total weight of the minimum spanning tree 计算最小生成树的总权重
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the undirected graph | 无向图
      Returns:
      total weight of MST | 最小生成树的总权重

    • totalWeight

      public static <V> double totalWeight(Set<Edge<V>> edges)
      Calculate the total weight of a set of edges 计算边集合的总权重
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      edges - the set of edges | 边集合
      Returns:
      total weight | 总权重

    • hasSpanningTree

      public static <V> boolean hasSpanningTree(Graph<V> graph)
      Check if a graph has a spanning tree (is connected) 检查图是否有生成树（是否连通）
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      true if graph is connected | 如果图连通返回true

    • minimumSpanningForest

      public static <V> Set<Edge<V>> minimumSpanningForest(Graph<V> graph)
      Find minimum spanning forest for disconnected graph 为不连通图查找最小生成森林
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      set of edges in the minimum spanning forest | 最小生成森林的边集合

    • componentCount

      public static <V> int componentCount(Graph<V> graph)
      Get the count of connected components after MST/MSF construction 获取MST/MSF构建后的连通分量数
      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph | 图
      Returns:
      number of connected components | 连通分量数