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数组表示每个节点的父节点。

相似文章
• 探索最小生成树算法的两种思路
  探索最小生成树算法的两种思路
  
  
• 关键词：最小生成树算法、Kruskal算法、Prim算法、数值计算
  关键词：最小生成树算法、Kruskal算法、Prim算法、数值计算
  
  
• 最小生成树：Kruskal算法和Prim算法的实现及时间复杂度分析
  最小生成树：Kruskal算法和Prim算法的实现及时间复杂度分析
  
  
• 最小生成树算法时间复杂度的分析和比较
  最小生成树算法时间复杂度的分析和比较
  
  
• 图论中的精髓——最小生成树Kruskal算法
  图论中的精髓——最小生成树Kruskal算法
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政