Java 实现 Prim 算法构建最小生成树

以下是使用 Java 代码实现 Prim 算法构建最小生成树的示例：

import java.util.*;

public class PrimAlgorithm {

    private static final int INF = Integer.MAX_VALUE; // 无穷大

    public static void main(String[] args) {
        int[][] graph = { // 图的邻接矩阵
                {0, 2, 4, INF, INF, INF},
                {2, 0, 6, 3, INF, INF},
                {4, 6, 0, 1, 5, INF},
                {INF, 3, 1, 0, 7, 8},
                {INF, INF, 5, 7, 0, 9},
                {INF, INF, INF, 8, 9, 0}
        };
        int n = graph.length; // 图的顶点数
        int[] parent = new int[n]; // 存储每个顶点在最小生成树中的父节点
        int[] dist = new int[n]; // 存储每个顶点到最小生成树的距离
        boolean[] visited = new boolean[n]; // 标记每个顶点是否已加入最小生成树

        // 初始化 dist 数组和 visited 数组
        Arrays.fill(dist, INF);
        Arrays.fill(visited, false);

        // 从顶点 0 开始构建最小生成树
        dist[0] = 0;
        parent[0] = -1; // 根节点没有父节点

        // 重复 n 次，每次加入一个顶点
        for (int i = 0; i < n; i++) {
            // 选取距离最小的未加入最小生成树的顶点
            int u = minDistance(dist, visited);
            visited[u] = true;

            // 更新与 u 相邻的顶点的距离和父节点
            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0 && !visited[v] && graph[u][v] < dist[v]) {
                    parent[v] = u;
                    dist[v] = graph[u][v];
                }
            }
        }

        // 输出最小生成树的边
        System.out.println('最小生成树的边：');
        for (int i = 1; i < n; i++) {
            System.out.println(parent[i] + ' - ' + i + '	' + graph[parent[i]][i]);
        }
    }

    // 返回距离最小的未加入最小生成树的顶点
    private static int minDistance(int[] dist, boolean[] visited) {
        int minDist = INF;
        int minIndex = -1;
        for (int i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                minIndex = i;
            }
        }
        return minIndex;
    }
}

运行结果：

最小生成树的边：
0 - 1	2
1 - 3	3
3 - 2	1
2 - 4	5
3 - 5	8

代码解释：

graph 数组： 存储图的邻接矩阵，表示各顶点之间的权重。
parent 数组： 用于存储每个顶点在最小生成树中的父节点。
dist 数组： 用于存储每个顶点到最小生成树的距离。
visited 数组： 用于标记每个顶点是否已加入最小生成树。
minDistance 函数： 用于返回距离最小的未加入最小生成树的顶点。

算法步骤：

初始化 dist 数组和 visited 数组，将所有顶点的距离设置为无穷大，标记为未加入最小生成树。
从顶点 0 开始构建最小生成树，将其距离设置为 0，标记为已加入最小生成树。
重复以下步骤 n 次，直到所有顶点都加入最小生成树：
- 找出距离最小的未加入最小生成树的顶点 u。
- 将顶点 u 加入最小生成树。
- 更新与 u 相邻的顶点的距离和父节点，如果它们更靠近最小生成树。
输出最小生成树的边，即每个顶点的父节点与其之间的权重。

总结：

Prim 算法是一种贪心算法，它每次都选择距离最小生成树最近的顶点加入到树中，最终构建出权重总和最小的生成树。该算法的时间复杂度为 O(n^2)，其中 n 为图的顶点数。

注意：

Prim 算法只适用于无向图，且要求图是连通的。如果图不连通，则需要对每个连通分量分别运行 Prim 算法。