Java实现Prim算法求最小生成树输出边集不符合预期问题排查

你代码里有3个核心bug，直接导致Prim算法选边逻辑失效：

• Java原生PriorityQueue不支持自动堆调整：你在遍历邻接边时直接修改了节点的key值，但没有触发堆重排，堆内部还是按照节点入堆时的旧key值排序，导致每次poll()取出的不是当前全局key最小的节点，完全违背Prim算法每次选跨集合最小边的逻辑。
• Node类的equals方法完全写废：
  • 方法里的!key.equals(key.name)是笔误，根本没有和传入的对比对象做属性比对
  • 用运行时动态变化的key作为相等判断依据完全错误，会导致PriorityQueue.contains()判断结果完全不准，出现节点重复、识别错误的问题
• KeyComparator存在空指针风险：平局排序时用了name字段，但Node初始化时name默认是null，运行到节点key相等的场景直接抛空指针异常。

修复方案 #

1. 重写Node类的相等判断逻辑 #

用节点初始化就赋值、全局唯一的abbrev字段作为hashCode和equals的判断依据，和动态变化的key、previous等运行时属性完全脱钩：

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((abbrev == null) ? 0 : abbrev.hashCode());
    return result;
}

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Node other = (Node) obj;
    if (abbrev == null) {
        return other.abbrev == null;
    } else return abbrev.equals(other.abbrev);
}

2. 修复KeyComparator空指针问题 #

平局排序改用初始化就非空的abbrev字段，避免name为null触发异常：

import java.util.Comparator;

public class KeyComparator implements Comparator<Node>{
    @Override
    public int compare(Node n, Node n1) {
        if(n.getKey() < n1.getKey())
            return -1;
        else if (n.getKey() > n1.getKey())
            return 1;
        else return n.getAbbrev().compareTo(n1.getAbbrev());
    }
}

3. 修正Prim核心逻辑，适配Java原生PriorityQueue的特性 #

不用自己实现复杂的decrease-key操作，用一个集合标记已经加入MST的节点，更新节点key后直接把新值的节点重新入堆，后续poll到堆里残留的旧key条目时直接跳过即可，这是JDK原生PQ实现Prim/Dijkstra的标准写法，简单不易错：

Comparator<Node> cm = new KeyComparator();
public ArrayList<Edge> MST_PRIM() {
    PriorityQueue<Node> Q = new PriorityQueue<>(graph.getNodeList().size(), cm);
    ArrayList<Edge> MST = new ArrayList<>();
    HashSet<Node> inMST = new HashSet<>(); // 标记已经确定加入MST的节点

    // 初始化所有节点属性
    for (Node n : graph.getNodeList()) {
        n.setKey(Integer.MAX_VALUE);
        n.setPreviousNode(null);
    }
    // 起始节点key设为0入堆
    Node start = graph.startingNode();
    start.setKey(0);
    Q.add(start);

    while (!Q.isEmpty()) {
        Node current = Q.poll();
        // 堆里残留的旧key条目，节点已经在MST里了直接跳过
        if (inMST.contains(current)) {
            continue;
        }
        inMST.add(current);

        // 非起始节点，把连向前驱的边加入MST结果集
        if (current.getPreviousNode() != null) {
            Edge connectEdge = current.findEdge(current.getPreviousNode());
            MST.add(connectEdge);
        }

        // 遍历所有邻接边，更新邻接节点的最小key
        for (Edge e : current.getOutgoingEdges()) {
            Node adjacent = e.getHead();
            if (!inMST.contains(adjacent) && e.getDistance() < adjacent.getKey()) {
                adjacent.setPreviousNode(e.getTail());
                adjacent.setKey(e.getDistance());
                // 更新后直接重新入堆，旧条目后续自动跳过
                Q.add(adjacent);
            }
        }
    }
    return MST;
}

注：原来逻辑里用Q.contains(v)判断节点是否在未访问集合的写法可以直接废弃，一方面PriorityQueue.contains()是O(n)时间复杂度效率低，另一方面用独立的inMST集合判断逻辑更清晰，不会受堆内重复元素的干扰。

内容的提问来源于stack exchange，提问作者Abshir M