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

Java实现最小生成树Prim算法

2023-06-11 02:29:47 深夜i 11 0

Java 最小生成树 Prim算法

最小生成树是求解一个无向连通图中所有边权值的和最小的生成树的算法，是图论中一个非常常用的算法。而Prim算法是其中一种求最小生成树的方法，与Kruskal算法一样，是一个贪心算法。

在Java中，我们可以使用Prim算法来求解最小生成树。首先需要定义一个数据结构来存储图中的节点和边，一般可以使用邻接矩阵或邻接表来存储。然后我们可以通过以下步骤来实现Prim算法：

1. 随机选取一个起始节点，并将其加入到最小生成树中。

2. 对于起始节点的所有邻接节点，将它们的边加入到一个最小堆中。

3. 从最小堆中取出一条边，如果该边的另一个节点不在最小生成树中，就将该节点加入到最小生成树中，并将该节点的所有邻接节点的边加入到最小堆中。

4. 重复步骤3，直到最小生成树包含所有的节点。

通过以上步骤，我们可以得到一个求解最小生成树的Java程序，具体实现可以参考下面的代码：

import java.util.*;
class Edge implements Comparable
  {
 
  int src, dest, weight;
  public int compareTo(Edge other) {
    return Integer.compare(this.weight, other.weight);
  }
}
public class Prim {
  public static void primMST(int[][] graph) {
    int V = graph.length;
    int[] parent = new int[V];
    int[] key = new int[V];
    boolean[] mstSet = new boolean[V];
    Arrays.fill(key, Integer.MAX_VALUE);
    Arrays.fill(mstSet, false);
    parent[0] = -1;
    key[0] = 0;
    PriorityQueue
  pq = new PriorityQueue<>();
 
    pq.add(new Edge(0, 0, 0));
    while (!pq.isEmpty()) {
      Edge e = pq.poll();
      int u = e.dest;
      if (mstSet[u])
        continue;
      mstSet[u] = true;
      for (int v = 0; v < V; v++) {
        if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
          parent[v] = u;
          key[v] = graph[u][v];
          pq.add(new Edge(u, v, graph[u][v]));
        }
      }
    }
    System.out.println("Edges of MST:");
    for (int i = 1; i < V; i++)
      System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
  }
  public static void main(String[] args) {
    int[][] graph = { 6, 0, 3, 8, 5 };
    primMST(graph);
  }
}

以上代码使用邻接矩阵存储图中的节点和边，利用优先队列实现最小堆来选择边。在main方法中，我们定义一个图，并调用primMST方法来求解最小生成树。运行程序，可以得到以下输出结果：

Edges of MST: 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5

以上即是使用Java实现最小生成树Prim算法的方法及代码。通过此算法可以快速求解无向连通图中的最优生成树，并可以应用于实际问题中。

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

下一篇: 作为一名java web开发者

评论区

相似文章