21xrx.com
2025-03-23 11:31:36 Sunday
文章检索 我的文章 写文章
使用Java实现最小生成树Kruskal算法
2023-06-11 13:48:47 深夜i     14     0
Java 最小生成树 Kruskal算法

Kruskal算法是一种常见的解决最小生成树问题的算法。本文介绍如何使用Java编写Kruskal算法的实现，并给出相应的代码案例。

Kruskal算法思路：

1. 将所有边按照边权从小到大排序。

2. 依次选取最小的边，若该边的两个端点不在同一连通块中，则将两个端点所在的连通块合并，该边成为最小生成树的边。

3. 重复步骤2，直至选取了n-1条边。

下面是Java实现Kruskal算法的代码：

import java.util.*;
public class Kruskal {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();  //节点数
    int m = sc.nextInt();  //边数
    int[][] edges = new int[m][3];
    for(int i=0;i
      edges[i][0] = sc.nextInt();  //起点
      edges[i][1] = sc.nextInt();  //终点
      edges[i][2] = sc.nextInt();  //边权
    }
    Arrays.sort(edges, (o1, o2) -> o1[2] - o2[2]); //按边权排序
    int[] parent = new int[n+1];  //并查集数组
    Arrays.fill(parent, -1);  //初始化
    List
  res = new ArrayList<>();
 
    int count = 0;
    for(int[] edge : edges){
      int x = find(parent, edge[0]);
      int y = find(parent, edge[1]);
      if(x != y){  //不在同一连通块中，加入最小生成树中
        res.add(edge);
        count++;
        if(count == n-1) break;  //选取了n-1条边，退出循环
        parent[x] = y;
      }
    }
    for(int[] r : res){
      System.out.println(r[0] + " " + r[1] + " " + r[2]);
    }
  }
  // 并查集查找
  public static int find(int[] parent, int x){
    if(parent[x] == -1) return x;
    parent[x] = find(parent, parent[x]);
    return parent[x];
  }
}

以上代码中使用了并查集实现了并查找，先将所有的节点初始化为-1，表示每个节点都是一个独立的连通块，每合并一个连通块，就将其中一个连通块的父节点指向另外一个连通块。在程序中用parent数组表示每个节点的父节点。

  
  

评论区