Java实现最小生成树算法 |21xrx.com

Java实现最小生成树算法

2023-06-12 01:05:22 深夜i -- --

最小生成树 Java Prim算法 Kruskal算法优先队列并查集

文章：最小生成树是图论中的一个经典问题，可以用于解决很多实际问题，如网络连通性、电路设计等。本文将介绍如何使用Java语言实现最小生成树算法。

首先，最小生成树是指在一个带权无向图中，找到一棵边权和最小的生成树。常见的算法有Prim算法和Kruskal算法。接下来，我们将分别介绍它们的实现过程。

一、Prim算法

Prim算法是基于点的贪心算法，每次选择一个离当前生成树最近的未加入生成树的点，并将该点相邻的边加入生成树。在Java中，可以使用Java集合框架中的优先队列（PriorityQueue）来实现。具体实现可以参考如下代码：


public void prim(int start) {
  PriorityQueue
  pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));
 
  boolean[] visited = new boolean[size];
  visited[start] = true;
  for (Edge edge : edges[start]) {
    pq.offer(edge);
  }
  while (!pq.isEmpty()) {
    Edge edge = pq.poll();
    if (visited[edge.to])
      continue;
    
    visited[edge.to] = true;
    weight += edge.weight;
    for (Edge nextEdge : edges[edge.to]) {
      if (!visited[nextEdge.to]) {
        pq.offer(nextEdge);
      }
    }
  }
}

二、Kruskal算法

Kruskal算法是基于边的贪心算法，每次选择一条最小的边，如果该边的两个端点不在同一个集合中，则将它们合并。可以使用并查集（Union-Find）数据结构来实现。具体实现可以参考如下代码：


public void kruskal() {
  UnionFind uf = new UnionFind(size);
  PriorityQueue
  pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));
 
  for (int i = 0; i < size; i++) {
    for (Edge edge : edges[i]) {
      pq.offer(edge);
    }
  }
  while (!pq.isEmpty()) {
    Edge edge = pq.poll();
    if (uf.find(edge.from) == uf.find(edge.to))
      continue;
    
    uf.union(edge.from, edge.to);
    weight += edge.weight;
  }
}

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

下一篇: 使用Java设计简单小游戏的步骤与技巧

评论区

()

相似文章