Kruskal算法是一种常用于最小生成树问题的算法，它基于贪心策略依次选择最小边，并保证不形成环，直到所有节点都被覆盖。下面我们将演示如何用Java实现Kruskal算法。

首先，我们需要定义一个边类Edge，表示图中两个节点之间的边，包括起点、终点和边的权重：

class Edge implements Comparable
  {
 
  int start, end, weight;
  public Edge(int s, int e, int w)
    start = s;
    end = e;
    weight = w;
  
  public int compareTo(Edge e)
    return weight - e.weight;
  
}

接着，我们需要实现一个并查集类UnionFind，用于检测是否形成环：

class UnionFind{
  int[] parent;
  public UnionFind(int n){
    parent = new int[n];
    for(int i = 0; i < n; i++){
      parent[i] = i;
    }
  }
  public int find(int p){
    while(p != parent[p]){
      parent[p] = parent[parent[p]];
      p = parent[p];
    }
    return p;
  }
  public void union(int p, int q){
    int rootP = find(p);
    int rootQ = find(q);
    parent[rootP] = rootQ;
  }
  public boolean connected(int p, int q){
    return find(p) == find(q);
  }
}

最后，我们可以调用Kruskal算法，并输出最小生成树的边：

public static List
  kruskal(int n, List 
  
   edges){
  
 
  Collections.sort(edges);
  UnionFind uf = new UnionFind(n);
  List
  mst = new ArrayList<>();
 
  for(Edge e : edges){
    int start = e.start;
    int end = e.end;
    if(!uf.connected(start, end)){
      uf.union(start, end);
      mst.add(e);
    }
    if(mst.size() == n - 1)
      break;
    
  }
  return mst;
}
public static void main(String[] args) {
  List
  edges = new ArrayList<>();
 
  edges.add(new Edge(0, 1, 4));
  edges.add(new Edge(0, 7, 8));
  edges.add(new Edge(1, 7, 11));
  edges.add(new Edge(1, 2, 8));
  edges.add(new Edge(2, 3, 7));
  edges.add(new Edge(2, 8, 2));
  edges.add(new Edge(2, 5, 4));
  edges.add(new Edge(3, 4, 9));
  edges.add(new Edge(3, 5, 14));
  edges.add(new Edge(4, 5, 10));
  edges.add(new Edge(5, 6, 2));
  edges.add(new Edge(6, 7, 1));
  edges.add(new Edge(6, 8, 6));
  edges.add(new Edge(7, 8, 7));
  List
  mst = kruskal(9, edges);
 
  for(Edge e : mst){
    System.out.println(e.start + "---" + e.end + "：" + e.weight);
  }
}

本文介绍了如何用Java实现Kruskal算法，在实际应用中，最小生成树求解可以帮助我们解决许多网络优化问题。本文的关键词有：Java、最小生成树、Kruskal算法。

相似文章
• ECMAScript和 Javascript的关系
  ECMAScript和 Javascript的关系
  
  

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