Java中用int[][] graph实现Prim算法邻接代价存储，graphi存i到j边权，无边时为Integer.MAX_VALUE；需双向赋值、对角线设为MAX_VALUE以统一处理。
在 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])。
例如：
inMST[u] = true;
for (int v = 0; v if (!inMST[v] && graph[u][v] != Integer.MAX_VALUE) {
minCost[v] = Math.min(minCost[v], graph[u][v]);
parent[v] = u; // 可选：记录 MST 边来源
}
}
空间与边界注意事项
邻接矩阵适合顶点数较少（如几百以内）的稠密图。若顶点数 n 很大但边稀疏，数组会浪费大量空间且遍历低效——此时应改用邻接表。使用数组时还需注意：
- 确保
graph是n × n方阵，索引从 0 开始，与顶点编号一致 - 输入边时做有效性检查：忽略自环（
u == v），重复边取较小权重 - Prim 起始点可任选（如 0），将
minCost[0] = 0，其余初始化为Integer.MAX_VALUE
一个极简可运行片段示意
以下代码片段展示关键结构定义与初始化逻辑（不含完整 Prim 循环）：
final int INF = Integer.MAX_VALUE;int n = 5;
int[][] graph = new int[n][n];
// 初始化为 INF
for (int i = 0; i Arrays.fill(graph[i], INF);
// 添加边：0-1(2), 0-3(6), 1-2(3), 1-3(8), 1-4(5), 2-4(7), 3-4(9)
int[][] edges = {{0,1,2},{0,3,6},{1,2,3},{1,3,8},{1,4,5},{2,4,7},{3,4,9}};
for (int[] e : edges) {
int u = e[0], v = e[1], w = e[2];
graph[u][v] = graph[v][u] = w;
}
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
