21xrx.com
2024-12-23 02:41:35 Monday
登录
文章检索 我的文章 写文章
Java实现最小生成树算法——Prim算法和Kruskal算法
2023-06-14 20:51:48 深夜i     --     --
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链接。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复