Java实现最小生成树算法——Prim算法和Kruskal算法 |21xrx.com

Java实现最小生成树算法——Prim算法和Kruskal算法

2023-06-14 20:51:48 深夜i 7 0

Java 最小生成树算法 Prim算法 Kruskal算法

最小生成树是一个具有重要应用性的算法，主要用于构建无向联通图的最小连通子图。本文将介绍两种基本的最小生成树算法——Prim算法和Kruskal算法，并介绍如何使用Java实现它们。

Prim算法：

Prim算法是一种基于贪心算法的思想，通过建立边界、选取最小边、更新边界这3个步骤找到最小生成树。具体实现如下所示：

public List
  prim(List 
  
   vertexList, List 
   
    edgeList) {
   
  
 
  List
  result = new ArrayList<>();
 
  Set
  visitedVertexSet = new HashSet<>();
 
  PriorityQueue
  priorityQueue = new PriorityQueue<>();
 
  Vertex startVertex = vertexList.get(0);
  visitedVertexSet.add(startVertex);
  while (visitedVertexSet.size() < vertexList.size()) {
    for (Edge edge : edgeList) {
      if (visitedVertexSet.contains(edge.getStartVertex()) &&
          !visitedVertexSet.contains(edge.getTargetVertex())) {
        priorityQueue.add(edge);
      }
    }
    Edge minEdge = priorityQueue.poll();
    if (minEdge == null)
      break;
    
    result.add(minEdge);
    visitedVertexSet.add(minEdge.getTargetVertex());
  }
  return result;
}

Kruskal算法：

Kruskal算法是基于并查集实现的，主要通过将所有的边按照权重从小到大排序，逐渐加入已选取的边集合中，防止形成环路，直到加入n-1条边，即为最小生成树。具体实现如下所示：

public List
  kruskal(List 
  
   vertexList, List 
   
    edgeList) {
   
  
 
  List
  result = new ArrayList<>();
 
  DisjointSet disjointSet = new DisjointSet(vertexList);
  PriorityQueue
  priorityQueue = new PriorityQueue<>(Comparator.comparing(Edge::getWeight));
 
  for (Edge edge : edgeList) {
    priorityQueue.add(edge);
  }
  while (!priorityQueue.isEmpty()) {
    Edge edge = priorityQueue.poll();
    Vertex startVertex = edge.getStartVertex();
    Vertex targetVertex = edge.getTargetVertex();
    if (disjointSet.find(startVertex.getNodeId()) != disjointSet.find(targetVertex.getNodeId())) {
      result.add(edge);
      disjointSet.union(startVertex.getNodeId(), targetVertex.getNodeId());
    }
  }
  return result;
}

本文介绍了两种基本的最小生成树算法，以及如何使用Java来实现算法。通过学习本文，读者可以掌握最小生成树算法的原理和实现。最后附上代码的GitHub链接。

上一篇: idea打包java可执行jar包

下一篇: Java面试：遇到的最大困难

评论区

相似文章