Java实现Kruskal算法的示例代码

Kruskal算法是一种求解最小生成树的贪心算法。这篇文章将提供Java语言实现Kruskal算法的示例代码以及完整攻略。

算法思路

Kruskal算法主要由以下两个步骤组成：

1. 初始化：将每个顶点作为单独的集合，将边按照权重从小到大排序。
2. 选择边：按照权重递增的顺序选择每条边，在不形成环的情况下将该边添加到最小生成树的边集中。

代码实现

以下是Java语言实现Kruskal算法的示例代码：

定义边的数据结构

class Edge implements Comparable<Edge> {
  int u, v, weight;

  public Edge(int u, int v, int weight) {
    this.u = u;
    this.v = v;
    this.weight = weight;
  }

  @Override
  public int compareTo(Edge o) {
    return weight - o.weight;
  }
}

定义并查集数据结构

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 x) {
    while (parent[x] != x) {
      parent[x] = parent[parent[x]]; // 优化，路径压缩
      x = parent[x];
    }
    return x;
  }

  public boolean union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if (rootX == rootY) {
      return false; // 已经连通
    }

    parent[rootX] = rootY;
    return true; // 未连通，合并成功
  }
}

实现Kruskal算法

public List<Edge> kruskal(List<Edge> edges, int n) {
  List<Edge> res = new ArrayList<>();
  UnionFind uf = new UnionFind(n);

  // 按照边的权重从小到大排序
  Collections.sort(edges);

  for (Edge edge : edges) {
    if (uf.union(edge.u, edge.v)) {
      res.add(edge);
    }
    if (res.size() == n - 1) {
      break;
    }
  }

  return res;
}

示例说明

示例1

输入：共有5个顶点和7条边，每条边的起点、终点和权重分别为：

(0,1,2), (0,3,6), (1,2,3), (1,3,8), (1,4,5), (2,4,7), (3,4,9)

输出：最小生成树的边集为：

(0,1,2), (1,2,3), (1,4,5), (0,3,6)

其中，(u, v, weight)表示从u到v的边权为weight。

示例2

输入：共有6个顶点和9条边，每条边的起点、终点和权重分别为：

(0,1,5), (0,2,1), (1,2,2), (1,3,5), (2,3,6), (2,4,3), (3,4,2), (3,5,7), (4,5,4)

输出：最小生成树的边集为：

(0,2,1), (1,2,2), (3,4,2), (4,5,4), (0,1,5)

总结

Kruskal算法是一种求解最小生成树的有效算法。本文提供了Java语言实现Kruskal算法的示例代码，并且提供了两个示例说明，希望能够帮助读者更好地理解和掌握Kruskal算法的实现过程。