Prime算法

邻接矩阵版推荐 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 } }