实现Kruskal算法时Java HashSet移除连通组件异常问题求助

问题分析 #

1. 连通组件集合类型错误

你使用Set<Set<Integer>>存储连通组件是核心问题：

• HashSet存储元素依赖于对象的hashCode()和equals()，而HashSet<Integer>的hashCode()是基于内部元素计算的。当执行startSet.addAll(endSet)修改startSet内容后，它的hashCode()会变化，导致HashSet无法正确定位该元素。
• 同时connectedComponents.remove(endSet)可能失效，因为HashSet无法通过修改后的hashCode找到原集合，导致endSet一直留在连通组件集合中。

2. 导致if(!startSet.equals(endSet))总是执行的原因

当connectedComponents.remove(endSet)失效时，endSet仍留在集合中。此时startSet已包含end节点，但endSet仍保留原有节点。后续遍历找end节点时会匹配到endSet，start节点匹配到startSet，两个集合内容不同，equals()返回false，导致if分支反复执行。

3. 查找逻辑效率低

原代码会遍历所有连通组件，即使已找到目标集合，既浪费资源也可能引发不必要的赋值问题。

修正后的代码 #

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.jgrapht.Graph;
import org.jgrapht.graph.AsSubgraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import java.util.PriorityQueue;

public class mySpanningTree {
    
    //Receives a graph and computes a minimum spanning tree
    public static AsSubgraph<Integer, DefaultWeightedEdge> computeMST(Graph<Integer, DefaultWeightedEdge> graph) {
        AsSubgraph<Integer, DefaultWeightedEdge> tree = new AsSubgraph<>(graph, graph.vertexSet(), new HashSet<>());

        PriorityQueue<DefaultWeightedEdge> edgeQueue = new PriorityQueue<>(Comparator.comparingDouble(graph::getEdgeWeight));
        edgeQueue.addAll(graph.edgeSet());
        
        // 改用List存储连通组件，基于引用管理元素，避免HashSet的hashCode问题
        List<Set<Integer>> connectedComponents = new ArrayList<>();
        for(Integer i : graph.vertexSet()){
            Set<Integer> set = new HashSet<>();
            set.add(i);
            connectedComponents.add(set);
        }
        
        int n = tree.vertexSet().size() - 1;
        while (!edgeQueue.isEmpty() && tree.edgeSet().size() < n) {
            DefaultWeightedEdge edge = edgeQueue.poll();
            Integer start = graph.getEdgeSource(edge);
            Integer end = graph.getEdgeTarget(edge);
            
            Set<Integer> startSet = null;
            Set<Integer> endSet = null;
            
            // 找到目标集合后立即终止循环，提升效率
            for(Set<Integer> set: connectedComponents){
                if(set.contains(start)){
                    startSet = set;
                }
                if(set.contains(end)){
                    endSet = set;
                }
                if(startSet != null && endSet != null){
                    break;
                }
            }
            
            // 空值判断，避免空指针异常
            if(startSet == null || endSet == null){
                continue;
            }
            
            if(!startSet.equals(endSet)){
                startSet.addAll(endSet);
                connectedComponents.remove(endSet);
                tree.addEdge(start, end, edge);
            }
        }
        return tree;
    }
}

关键修改说明 #

• 替换连通组件集合类型：将Set<Set<Integer>>改为List<Set<Integer>>，List基于对象引用管理元素，修改集合内容不会影响元素定位，remove(endSet)可准确移除目标集合。
• 优化查找逻辑：找到start和end所属集合后立即终止循环，减少不必要的遍历。
• 增加空值防护：防止极端情况下找不到集合导致的空指针异常。

修改后，连通组件的合并与移除操作可正常工作，if(!startSet.equals(endSet))也能正确判断节点是否属于同一连通组件，避免无效边的添加。

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