prim算法 Java

### 关于Java实现Prim算法

#### 使用邻接矩阵表示图的数据结构
为了方便理解，在此提供一种基于邻接矩阵来存储无向加权图的方式。对于每一个节点，通过二维数组`graph[][]`保存与其他节点之间的权重关系；如果两个节点间不存在边，则设置其值为无穷大（即一个非常大的数）。同时定义了一个辅助数组`parent[]`用于追踪构建过程中各顶点对应的父节点位置[^3]。

public class PrimAlgorithm {
    private static final int INF = Integer.MAX_VALUE;
    
    public void prim(int[][] graph, int startVertex){
        int numVertices = graph.length; // 获取顶点数量
        boolean[] visited = new boolean[numVertices]; // 记录访问状态
        int[] parent = new int[numVertices];          // 存储MST中的前驱结点
        int[] key = new int[numVertices];             // 各个顶点到集合S的最短距离
        
        Arrays.fill(key, INF);                        // 初始化key数组，默认最大值
        Arrays.fill(parent, -1);                      // 初始状态下所有顶点都没有前驱结点
        key[startVertex] = 0;                         // 起始顶点的距离设为0
        
        for (int count = 0; count < numVertices - 1; ++count) { // 进行n-1次迭代
            int u = minKey(key, visited);
            
            visited[u] = true;

            for (int v = 0; v < numVertices; ++v){      // 更新相邻未处理过的顶点
                if (!visited[v] && graph[u][v]!=INF &&
                    graph[u][v] < key[v]){
                       parent[v]=u;
                       key[v]=graph[u][v];
                   }
               }
           }

       }

       private int minKey(int[] keys,boolean[] mstSet){
           int min = INF,min_index=-1;
           
           for (int i=0;i<keys.length;++i)
              if(!mstSet[i]&&keys[i]<min){
                  min=keys[i];
                  min_index=i;
              }
              
           return min_index;
       }
}

上述代码展示了如何利用Java编程语言完成Prim算法的具体操作流程，并且解释了其中涉及到的关键变量含义及其作用机制。这段程序能够有效地计算给定连通网络内的最小生成树(Minimum Spanning Tree)，并返回构成该树所需选取的所有边以及它们所连接的端点信息[^2]。