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

Java语言下最小生成树算法Prim的实现

2023-06-17 14:10:46 深夜i -- --

Java语言最小生成树 Prim算法贪心算法最小堆

Java语言在算法设计与实现方面具有较高的应用价值，其中最小生成树算法Prim具有广泛的应用场景。本文将介绍Java语言下Prim算法的实现过程，并提供代码示例。

Prim算法是一种贪心算法，它的核心思想是寻找图中的最小生成树，即连接所有顶点且总权值最小的树。Prim算法主要思路是从某一起点开始依次加入与该点相邻的最短边，直到遍历所有节点为止，最后得到的就是该图的最小生成树。

在Java语言下实现Prim算法，需要进行以下几个步骤：

1.构建最小堆：将图中所有节点添加进堆中，并构建最小堆，用以按照边权值从小到大依次取出；

2.选择初始点：从堆中随机取出一个节点作为初始点；

3.遍历相邻节点：取出堆顶节点后，遍历该节点相邻的所有节点，并将相邻节点与它的边权值加入堆中；

4.选取最短边：按照边权值从小到大依次取出堆中的边，若该边连接的节点均未被访问，则该边为所选边；

5.标记节点：将选取的边连接的两个节点标记为已访问；

6.继续遍历：重复3~5步骤，直到所有节点均被标记。

利用以上步骤，即可实现Prim算法。下面是Java代码示例：


public class Prim {
  public static void main(String[] args) {
    int[][] graph = {0, 1, 3, 4}; // 测试图
    int[] visited = new int[graph.length]; // 记录节点是否已访问
    visited[0] = 1; // 从第一个节点开始遍历
    List
  edges = new ArrayList<>(); // 保存最小生成树的边
 
    PriorityQueue
  heap = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]); // 构建最小堆
 
    for (int i = 0; i < graph.length; i++) {
      if (graph[0][i] != 0) {
        heap.offer(new int[]{0, i, graph[0][i]});
      }
    }
    while (edges.size() < graph.length - 1 && !heap.isEmpty()) { // 遍历所有节点
      int[] edge = heap.poll();
      if (visited[edge[0]] == 0 || visited[edge[1]] == 0) { // 若该边连接的节点均未被访问，则该边为最小生成树的边
        edges.add(edge);
        visited[edge[0]] = 1;
        visited[edge[1]] = 1;
        for (int i = 0; i < graph.length; i++) { // 遍历相邻节点
          if (graph[edge[1]][i] != 0 && visited[i] == 0) {
            heap.offer(new int[]{edge[1], i, graph[edge[1]][i]});
          }
        }
      }
    }
    System.out.println("最小生成树的边为：");
    for (int[] edge : edges) {
      System.out.println(edge[0] + "-" + edge[1] + ":" + edge[2]);
    }
  }
}

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

下一篇: C语言中max函数的含义及相关应用

评论区

()

相似文章