Java图论进阶之最小生成树算法详解

在图论中，最小生成树(Minimum Spanning Tree, MST) 是连接所有图节点的一棵树，其边的权重和最小。本文将介绍最常见的两种求最小生成树的算法——Prim算法和Kruskal算法。

Prim算法

Prim算法以一个初始节点为起点，每次选择距离该节点最近的未访问节点加入生成树中，直至生成一棵生成树，时间复杂度为O(n^2)。

1. 节点距离数组初始化为非常大的值，起点距离初始化为0。
2. 选择未访问节点中距离起点最近的节点并标记为已访问。
3. 如果当前节点已被访问，则跳过该节点。
4. 更新距离数组和父节点数组。
5. 重复步骤2-4，直至所有节点均被访问。

Prim算法实现

以下是Prim算法的Java实现示例：

public static int prim(int[][] graph, int n) {
    int[] dist = new int[n]; // 节点距离数组
    boolean[] visited = new boolean[n]; // 节点是否访问过数组

    Arrays.fill(dist, Integer.MAX_VALUE); // 初始化节点距离为无限大
    dist[0] = 0; // 起点距离初始化为0

    for (int i = 0; i < n - 1; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        visited[u] = true;
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != 0 && graph[u][v] < dist[v]) {
                dist[v] = graph[u][v];
            }
        }
    }

    int ans = 0;
    for (int d : dist) {
        ans += d;
    }
    return ans;
}

Kruskal算法

Kruskal算法以所有边构成的集合为初始状态，每次选择权重最小的边加入生成树中，并更新集合，直至生成一棵生成树，时间复杂度为O(mlogm)。

1. 创建一个空的优先队列，并将图中所有边加入队列。
2. 初始化并查集。
3. 从队列中取出最小边。
4. 如果加入该边不会形成环，则加入生成树中，并更新并查集中的元素。
5. 重复步骤3-4，直至生成一棵生成树。

Kruskal算法实现

以下是Kruskal算法的Java实现示例：

public static int kruskal(int[][] graph, int n) {
    PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[2] - b[2]); // 权重最小的边优先队列

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (graph[i][j] != 0) {
                queue.offer(new int[]{i, j, graph[i][j]}); // 将图中所有边加入队列
            }
        }
    }

    UnionFind uf = new UnionFind(n); // 初始化并查集

    int ans = 0;
    while (!queue.isEmpty()) {
        int[] edge = queue.poll();
        int u = edge[0], v = edge[1], w = edge[2];
        if (uf.find(u) != uf.find(v)) { // 如果加入该边不会形成环
            ans += w;
            uf.union(u, v);
        }
    }
    return ans;
}

示例说明

假设有以下无向带权图：

     7       2
 A-------B-------C
 |      / \
8|   /     \4
 | /        \
 D-------E---F
      9

邻接矩阵表示为:

    A   B   C   D   E   F
 A  0   7   0   8   0   0
 B  7   0   2   0   4   0
 C  0   2   0   0   0   9
 D  8   0   0   0   9   0
 E  0   4   0   9   0   6
 F  0   0   9   0   6   0

使用Prim算法得到的最小生成树为：

     7       2
 A-------B-------C
          \
          4
           \
            E---F
             6

使用Kruskal算法得到的最小生成树为：

       2           4
 B-------C-------F
 |       |       |
 7       2       6
 |       |       |
 A       E-------D
         9

结论

两种算法的时间和空间复杂度不同，适用于不同情况。Prim算法效率相对较高，适合边比较少的图；Kruskal算法适合边比较多的图。