邻接矩阵版（推荐 n≤5000，稠密图）
时间复杂度O(n2)，无需预建邻接矩阵，动态计算边权（适配圆形 / 坐标类场景），是算法题中最常用的版本。
import java.util.Arrays; /** * Prim算法模板（邻接矩阵版，动态计算边权） * 适用场景：节点数n≤5000的稠密图，边权可动态计算（如坐标类问题） * @param n 节点总数 * @param nodes 节点信息数组（可根据场景自定义，比如圆形的x/y/r） * @return 最小生成树的总权重 */ public class PrimTemplate { // 示例：适配圆形场景的节点结构（可根据实际需求修改） static class Node { int x, y, r; Node(int x, int y, int r) { this.x = x; this.y = y; this.r = r; } } // 核心Prim算法实现（动态计算边权） public static double prim(int n, Node[] nodes) { // 1. 初始化核心数组 boolean[] vis = new boolean[n]; // 标记节点是否加入已选集合 double[] minDist = new double[n]; // 记录每个节点到已选集合的最小距离 Arrays.fill(minDist, Double.MAX_VALUE); // 初始化为无穷大 minDist[0] = 0.0; // 选0号节点作为起点 double totalWeight = 0.0; // 最小生成树总权重 // 2. 主循环：依次选择n个节点加入集合 for (int i = 0; i < n; i++) { // 步骤1：找到未访问、距离已选集合最近的节点u int u = -1; double minVal = Double.MAX_VALUE; for (int j = 0; j < n; j++) { if (!vis[j] && minDist[j] < minVal) { minVal = minDist[j]; u = j; } } // 防御性判断：所有节点已选（n≥1时不会触发） if (u == -1) break; // 步骤2：将u加入已选集合，累加权重 vis[u] = true; totalWeight += minVal; // 步骤3：松弛操作——更新所有未访问节点的最小距离 for (int v = 0; v < n; v++) { if (!vis[v]) { // ========== 关键：根据场景自定义边权计算逻辑 ========== // 示例：圆形场景的边权 = max(0, 圆心距离 - 两圆半径和) long dx = nodes[u].x - nodes[v].x; long dy = nodes[u].y - nodes[v].y; double centerDist = Math.sqrt(dx * dx + dy * dy); double edgeWeight = Math.max(0.0, centerDist - nodes[u].r - nodes[v].r); // 其他场景示例（如普通邻接矩阵）： // double edgeWeight = graph[u][v]; // graph是预定义的邻接矩阵 // 更新最小距离 if (edgeWeight < minDist[v]) { minDist[v] = edgeWeight; } } } } return totalWeight; } // 测试示例（圆形连接场景） public static void main(String[] args) { int n = 3; // 3个圆形节点 Node[] nodes = new Node[n]; nodes[0] = new Node(0, 0, 1); nodes[1] = new Node(3, 0, 1); nodes[2] = new Node(6, 0, 1); double result = prim(n, nodes); System.out.printf("最小生成树总权重：%.2f\n", result); // 输出：2.00 } }
