Java邻接矩阵实现Prim最小生成树算法存在Bug：仅选中初始顶点无法扩展

我仔细看了你的Prim算法实现，发现导致程序一直重复选中0-1这条边、无法扩展到其他顶点的问题主要有两个：

问题分析 #

1. minimum变量未在循环内重置
   你在方法开头把minimum初始化为Integer.MAX_VALUE，但在每次while循环迭代中没有重新设置它的初始值。第一次循环找到最小边0-1（权重1）后，minimum就一直保持1，后续循环里所有其他边的权重都比1大，所以程序只会不断选中这条已选过的边。

2. MST总权重累加时机错误
   你在每次发现更小边时就执行MST_weight += adjMatrix[i][j]，但实际上应该是在确定选中这条边并将顶点加入MST后才累加权重。原代码中每次循环都会重复累加这条边的权重，导致最终总权重计算错误。

修正后的代码 #

下面是修复了这两个问题的primsMST方法：

public void primsMST(){
    int MST_weight = 0;
    boolean[] selected = new boolean[this.V];
    Arrays.fill(selected, false);
    int no_of_edges = 0;
    int x = 0;
    int y = 0;
    int max_edges = V - 1;

    selected[0] = true;
    System.out.println("Selected Edges in a Minimum Spanning Tree are:");

    while(no_of_edges < max_edges){
        // 每次循环开始时重置minimum为最大值，确保能找到当前未选边中的最小值
        int minimum = Integer.MAX_VALUE;
        // 重置x和y，避免保留上一次的边
        x = -1;
        y = -1;

        for(int i = 0; i < V; i++){
            if(selected[i]){
                for(int j = 0; j < V; j++){
                    if(!selected[j] && adjMatrix[i][j] != 0){
                        if(adjMatrix[i][j] < minimum){
                            minimum = adjMatrix[i][j];
                            x = i;
                            y = j;
                        }
                    }
                }
            }
        }

        // 确认找到有效边后再累加权重并输出
        if(x != -1 && y != -1){
            System.out.println(x + "-" + y + " : " + adjMatrix[x][y]);
            MST_weight += minimum;
            selected[y] = true;
            no_of_edges++;
        }
    }
    System.out.println("Total weight of the Minimum Spanning Tree is " + MST_weight);
}

修正后的输出 #

运行你的测试用例后，输出会变成：

Selected Edges in a Minimum Spanning Tree are:
0-1 : 1
0-2 : 2
2-3 : 4
Total weight of the Minimum Spanning Tree is 7

这个结果符合Prim算法的预期：最小生成树的边是0-1（1）、0-2（2）、2-3（4），总权重为7。

备注：内容来源于stack exchange，提问作者Sree Teja