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

Java Prim算法：最小生成树的实现

2023-09-13 04:12:08 深夜i -- --

Java Prim算法最小生成树实现算法

Java Prim算法是一种用于查找最小生成树的算法。在计算机科学中，最小生成树是指连接图中所有顶点的一棵树，其边的权重之和最小。Prim算法通过逐步选择边来构建最小生成树，直到所有顶点都被连接。

Java Prim算法的实现可以分为以下几个步骤：

1. 创建一个空的最小生成树MST和一个空的优先队列PQ。

2. 随机选择一个起始顶点，将其加入MST中。

3. 将起始顶点的所有边加入PQ中，并按照权重从小到大的顺序排列。

4. 从PQ中选择权重最小的边，将其加入MST中。

5. 将新加入的边的终点的所有边加入PQ中（如果不在MST中），并按照权重从小到大的顺序排列。

6. 重复步骤4-5，直到所有顶点都被连接。

下面是一个示例的Java代码实现：


import java.util.*;
public class PrimAlgorithm {
  public static void primMST(int[][] graph) {
    int numVertices = graph.length;
    boolean[] visited = new boolean[numVertices];
    int[] parent = new int[numVertices];
    int[] key = new int[numVertices];
    Arrays.fill(key, Integer.MAX_VALUE);
    key[0] = 0;
    parent[0] = -1;
    for (int i = 0; i < numVertices - 1; i++) {
      int minKey = getMinimumKey(key, visited);
      visited[minKey] = true;
      for (int j = 0; j < numVertices; j++) {
        if (graph[minKey][j] != 0 && !visited[j] && graph[minKey][j] < key[j]) {
          parent[j] = minKey;
          key[j] = graph[minKey][j];
        }
      }
    }
    
    printMST(parent, graph);
    System.out.println("MST weight: " + calculateWeight(parent, graph));
  }
  private static int getMinimumKey(int[] key, boolean[] visited) {
    int minKey = Integer.MAX_VALUE;
    int minIndex = -1;
    for (int i = 0; i < key.length; i++) {
      if (!visited[i] && key[i] < minKey) {
        minKey = key[i];
        minIndex = i;
      }
    }
    return minIndex;
  }
  private static void printMST(int[] parent, int[][] graph) {
    System.out.println("Minimum Spanning Tree:");
    for (int i = 1; i < graph.length; i++) {
      System.out.println(parent[i] + " - " + i + "\t\t" + graph[i][parent[i]]);
    }
  }
  
  private static int calculateWeight(int[] parent, int[][] graph) {
    int weight = 0;
    
    for (int i = 1; i < graph.length; i++) {
      weight += graph[i][parent[i]];
    }
    
    return weight;
  }
  public static void main(String[] args) {
    int[][] graph = {
       6,
       5,
       3,
       0,
       0
    };
    primMST(graph);
  }
}

在上面的示例中，我们使用邻接矩阵表示图，并对其应用Prim算法。通过运行这段代码，我们可以得到计算出的最小生成树以及其权重。

总之，Java Prim算法是一种非常有效的方法，用于计算图中的最小生成树。它的时间复杂度为O(V^2)，其中V为顶点的数量。通过合理的数据结构和算法设计，我们可以实现高效的最小生成树计算。

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

下一篇: FFmpeg推流时没有sps？解决方法分享

评论区

()

相似文章