当前位置：首页 > 文章列表 > 文章 > java教程 > Java数组实现Prim算法邻接代价存储方法

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

2026-05-27 14:30:44 0浏览收藏

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

如何在 Java 中利用数组实现简单的最小生成树 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])。

例如：

int u = findMinIndex(minCost, inMST); // 找当前未入树且 minCost 最小的顶点
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数组实现Prim算法邻接代价存储方法》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！