Java语言基于无向有权图实现克鲁斯卡尔算法代码示例

Java语言基于无向有权图实现克鲁斯卡尔算法代码示例，可以分为下面几个步骤：

1. 了解克鲁斯卡尔算法

克鲁斯卡尔算法是一种用于求解最小生成树（Minimum Spanning Tree，简称MST）的算法，其通过按边权非递减的顺序将所有边加入生成树中。对于每一条边，都需判断它所在的两个点是否在同一个集合中，如果不在，则将它们合并，同时将边加入生成树中。

2. 实现克鲁斯卡尔算法

2.1 定义数据结构

对于这个算法，我们需要定义一个Edge类来表示图的边，同时定义一个UnionFind类来表示并查集，用于管理节点所属的集合。

public class Edge implements Comparable<Edge> {
    int v, w; // 边的两个顶点
    double weight; // 边的权值

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

    // 按照边权升序排序
    public int compareTo(Edge that) {
        if (this.weight < that.weight) return -1;
        else if (this.weight > that.weight) return 1;
        else return 0;
    }
}

public class UnionFind {
    private int[] parent; // 存储父节点的数组

    public UnionFind(int size) {
        parent = new int[size];
        for (int i = 0; i < size; 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);

        if (rootP == rootQ) return;

        parent[rootP] = rootQ; // 将rootP的根节点设为rootQ
    }
}

2.2 实现算法

有了边和并查集这两个基础数据结构，我们就可以实现克鲁斯卡尔算法了。

public class KruskalMST {
    private Queue<Edge> mst; // 最小生成树的边
    private UnionFind uf; // 并查集
    private double weight; // 最小生成树的权重

    public KruskalMST(EdgeWeightedGraph G) {
        mst = new LinkedList<>();
        uf = new UnionFind(G.V());

        // 将所有边加入优先队列
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        for (Edge e : G.edges()) {
            pq.offer(e);
        }

        // 从小到大处理每一条边
        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge e = pq.poll();
            int v = e.v, w = e.w;

            // 如果两个顶点不在同一个集合中，则加入最小生成树
            if (uf.find(v) != uf.find(w)) {
                uf.union(v, w);
                mst.offer(e);
                weight += e.weight;
            }
        }
    }

    // 返回最小生成树的所有边
    public Iterable<Edge> edges() {
        return mst;
    }

    // 返回最小生成树的权重
    public double weight() {
        return weight;
    }
}

3. 示例说明

3.1 示例一

假设有以下的无向加权图，用于测试克鲁斯卡尔算法是否正确。

  7 - 8 
 /   / | \
4 - 5 - 6 - 7 
|   |   |   |
0 - 1 - 2 - 3

实现如下：

EdgeWeightedGraph G = new EdgeWeightedGraph(9);
G.addEdge(new Edge(0, 1, 10));
G.addEdge(new Edge(1, 2, 10));
G.addEdge(new Edge(2, 3, 10));
G.addEdge(new Edge(3, 6, 10));
G.addEdge(new Edge(6, 7, 10));
G.addEdge(new Edge(7, 8, 10));
G.addEdge(new Edge(8, 5, 10));
G.addEdge(new Edge(5, 4, 10));
G.addEdge(new Edge(4, 0, 10));

KruskalMST mst = new KruskalMST(G);
System.out.println(mst.weight());
for (Edge e : mst.edges()) {
    System.out.println(e.v + "-" + e.w);
}

输出结果：

60.0
0-1
1-2
2-3
5-4
3-6
6-7
7-8

可以看出，输出的最小生成树是正确的，权重为60。

3.2 示例二

再看以下的无向加权图，用于测试克鲁斯卡尔算法是否正确。

-------6--------
|\     |     /|
3  \   2   /  3
|    \ | /    |
0-----  1----- 5
|    / | \    |
3  /   4   \  2
| /     |     \|
-------7--------