Java求最小生成树的两种算法详解

概述

最小生成树（Minimum Spanning Tree）是指在一张连通的、有权图中找到一棵权值和最小的生成树，它是一些算法的子问题，常用于解决带权无向图的问题。常见的最小生成树算法有Prim算法和Kruskal算法，本文将详细讲解这两种算法的实现原理及其Java代码实现。

Prim算法

Prim算法是一种贪心算法，通过每次选择当前权值最小的边来构建最小生成树。具体实现过程如下：

1. 从任意一个节点出发，将其加入生成树中。
2. 找到与树相邻的最小权值的边，并将其连接到树上。
3. 将该边连接的节点加入生成树中。
4. 重复步骤2和步骤3，直到所有的节点都被加入生成树中。

下面是Prim算法的Java实现，其中graph是一个存储图信息的二维数组，n是图中节点的个数：

int prim(int[][] graph, int n) {
    int[] dis = new int[n];  // 存储每个节点到已选择节点的最短距离
    boolean[] vis = new boolean[n];  // 存储每个节点是否已经被选择
    Arrays.fill(dis, Integer.MAX_VALUE);
    dis[0] = 0;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {  // 找到未被选择节点中距离已选择节点最近的节点
            if (!vis[j] && (u == -1 || dis[j] < dis[u])) {
                u = j;
            }
        }
        vis[u] = true;
        ans += dis[u];  
        for (int v = 0; v < n; v++) {  // 更新未被选择节点的最短距离
            if (!vis[v]) {
                dis[v] = Math.min(dis[v], graph[u][v]);
            }
        }
    }
    return ans;
}

示例1：给定以下五个节点之间的连通情况和边权值，求最小生成树的权值和。

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

其中graph矩阵如下：

int[][] graph = {
        {0, 2, Integer.MAX_VALUE, Integer.MAX_VALUE, 1, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
        {2, 0, 4, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
        {Integer.MAX_VALUE, 4, 0, 5, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 3},
        {Integer.MAX_VALUE, Integer.MAX_VALUE, 5, 0, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 4},
        {1, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
        {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0, 6, Integer.MAX_VALUE},
        {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 6, 0, 7},
        {Integer.MAX_VALUE, Integer.MAX_VALUE, 3, 4, Integer.MAX_VALUE, Integer.MAX_VALUE, 7, 0}
};
int ans = prim(graph, 8);
System.out.println(ans);

输出：10，表示最小生成树的权值和为10。

Kruskal算法

Kruskal算法是一种基于贪心的算法，通过不断选择图中权值最小的边来构建最小生成树。具体实现过程如下：

1. 将所有的边按权值从小到大排序。
2. 依次选择每条边，如果该边不会与已经选择的边构成环，则将其加入生成树中，否则忽略该边。
3. 重复步骤2，直到生成树的边数为n-1。

下面是Kruskal算法的Java实现，其中graph是一个存储图信息的二维数组，n是图中节点的个数：

class Edge implements Comparable<Edge> {
    int from, to, w;
    Edge(int f, int t, int w) {
        this.from = f;
        this.to = t;
        this.w = w;
    }
    @Override
    public int compareTo(Edge o) {  // 重写比较函数
        return w - o.w;  // 按边的权值从小到大排序
    }
}
int kruskal(int[][] graph, int n) {
    Edge[] edges = new Edge[n * (n - 1) / 2];  // 存储所有的边
    int idx = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (graph[i][j] != Integer.MAX_VALUE) {
                edges[idx++] = new Edge(i, j, graph[i][j]);
            }
        }
    }
    Arrays.sort(edges);  // 按边的权值从小到大排序
    int ans = 0;
    int[] uf = new int[n];
    for (int i = 0; i < n; i++) {
        uf[i] = i;
    }
    for (Edge e : edges) {
        int fu = find(e.from, uf);
        int fv = find(e.to, uf);
        if (fu == fv) {  // 若加入该边会形成环，则忽略该边
            continue;
        }
        uf[fu] = fv;
        ans += e.w;
    }
    return ans;
}
int find(int x, int[] uf) {
    if (x != uf[x]) {
        uf[x] = find(uf[x], uf);  // 路径压缩
    }
    return uf[x];
}

示例2：和示例1中的图相同，求最小生成树的权值和，但采用Kruskal算法。

int[][] graph = {
        {0, 2, Integer.MAX_VALUE, Integer.MAX_VALUE, 1, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
        {2, 0, 4, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
        {Integer.MAX_VALUE, 4, 0, 5, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 3},
        {Integer.MAX_VALUE, Integer.MAX_VALUE, 5, 0, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 4},
        {1, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
        {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0, 6, Integer.MAX_VALUE},
        {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 6, 0, 7},
        {Integer.MAX_VALUE, Integer.MAX_VALUE, 3, 4, Integer.MAX_VALUE, Integer.MAX_VALUE, 7, 0}
};
int ans = kruskal(graph, 8);
System.out.println(ans);

输出：10，表示最小生成树的权值和为10。

总结

本篇文章详细讲解了Prim算法和Kruskal算法的实现原理及其Java代码实现，并分别进行了两个示例的说明。这两种算法都可以在处理带权无向图的最小生成树问题上得到良好的应用。