Java数组实现Prim算法邻接代价存储方法

本文深入解析了在Java中使用二维整型数组（int[][]）实现Prim最小生成树算法时的邻接代价存储策略：通过以Integer.MAX_VALUE统一表示不存在的边和自环，配合双向赋值保证无向图对称性，使邻接矩阵既能支持O(1)边权查询、简化minCost更新逻辑，又避免了-1或0等值与合法权重的语义冲突；同时指出该方案适用于中小规模稠密图，并强调了初始化规范、边界处理及稀疏场景下的替代建议，为高效、健壮地实现Prim算法提供了清晰可靠的底层数据结构支撑。

在 Java 中用数组实现 Prim 算法的邻接代价存储，核心是用二维数组 int[][] graph 表示带权无向图的邻接矩阵，其中 graph[i][j] 存储顶点 i 到 j 的边权；若无边，则设为一个足够大的值（如 Integer.MAX_VALUE），而非 -1 或 0，避免与合法边权混淆。

邻接矩阵的初始化与约定

Prim 算法依赖快速查某顶点到其他所有顶点的边权，邻接矩阵天然支持 O(1) 查询。需注意：

• 图是无向的，因此 graph[i][j] == graph[j][i]，初始化时需双向赋值
• 对角线元素 graph[i][i] 应设为 0（自环不参与 MST）或 Integer.MAX_VALUE（统一表示“不可达”），推荐后者以简化逻辑
• 不存在的边统一用 Integer.MAX_VALUE，便于后续用 Math.min() 和条件判断（如 if (weight ）

Prim 主循环中如何使用该数组

Prim 维护两个关键数组：boolean[] inMST 标记顶点是否已加入生成树，int[] minCost 记录各顶点到当前 MST 的最小邻接边权。邻接矩阵在此处的作用是：每次新加入一个顶点 u 后，遍历所有未加入的顶点 v，更新 minCost[v] = Math.min(minCost[v], graph[u][v])。

例如：

空间与边界注意事项

邻接矩阵适合顶点数较少（如几百以内）的稠密图。若顶点数 n 很大但边稀疏，数组会浪费大量空间且遍历低效——此时应改用邻接表。使用数组时还需注意：

• 确保 graph 是 n × n 方阵，索引从 0 开始，与顶点编号一致
• 输入边时做有效性检查：忽略自环（u == v），重复边取较小权重
• Prim 起始点可任选（如 0），将 minCost[0] = 0，其余初始化为 Integer.MAX_VALUE

一个极简可运行片段示意

以下代码片段展示关键结构定义与初始化逻辑（不含完整 Prim 循环）：

好了，本文到此结束，带大家了解了《Java数组实现Prim算法邻接代价存储方法》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！