实现 Kruskal 算法时从 Java-HashSet 中删除的问题

Question

在下面的代码中，我尝试实现 Kruskal 算法来计算图的最小生成树。

问题是从连接的组件中删除集合无法正常工作，并且 if(!startSet.equals(endSet)) 似乎总是被执行。

现在是代码：

    import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
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<Integer, DefaultWeightedEdge>(graph, graph.vertexSet(), new HashSet<DefaultWeightedEdge>());

        PriorityQueue<DefaultWeightedEdge> edgeQueue = new PriorityQueue<>(Comparator.comparingDouble(graph::getEdgeWeight));
        edgeQueue.addAll(graph.edgeSet());
        Set<Set<Integer>> connectedComponents = new HashSet<>();
        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.equals(endSet)){
                startSet.addAll(endSet);
                connectedComponents.remove(endSet);
                tree.addEdge(start, end, edge);
            }
            else{
            }
        }
        return tree;
    }

代码的想法是跟踪集合中的连接组件。每当一条边连接来自不同连接组件的两个节点时，我想合并这两个连接组件并将结果存储在集合中，而不是之前的两个组件。此外，还应添加边缘。 每当一条边在同一个集合中有两个端点时，就不应添加它（因为添加它会创建一个循环）。

如有任何帮助，我们将不胜感激！

Answer 1

这里必须在create之前使用from接口

    interface A{
int set1{
Set<Integer> set = new HashSet<>();
set.add(i);
return set;
   }
}
interface B extends A{
    Set<Integer> connectedComponents = new HashSet<>();
for(Integer i : graph.vertexSet()){
            Set<Integer> set = new HashSet<>();
            set.add(i);
            connectedComponents.add(set);
        }

...等等。这样你就可以一步步解决问题。

Answer 2

connectedComponents

的值是一个可变集合，其元素也是可变集合。问题是，通过破坏性地修改

connectedComponents

的元素而不“通知”容器，容器的数据结构会悄然损坏。

尝试在变异之前从

connectedComponents

中删除元素集，然后将其添加回来：

if(!startSet.equals(endSet)){
    connectedComponents.remove(startSet);  // Added back below ...
    connectedComponents.remove(endSet);
    startSet.addAll(endSet);
    connectedComponents.add(startSet);     // ... right here
    tree.addEdge(start, end, edge);
}

或者，它可能有助于使用不同的容器（例如

IdentityHashMap

）来跟踪元素集（使用您喜欢的任何值作为值）。这在这里可行，因为您不需要容器通过内容跟踪元素集（就像

HashSet

隐式所做的那样）。

例如：

IdentityHashMap<Set<Integer>, Object> connectedComponents = new IdentityHashMap<>();

...

for(Integer i : graph.vertexSet()){
    Set<Integer> set = new HashSet<>();
    set.add(i);
    connectedComponents.put(set, set);
}

...

for(Set<Integer> set: connectedComponents.keySet()) {
    ...
    if(set.contains(start)){
        startSet = set;
    }
    if(set.contains(end)){
        endSet = set;
    }
}

if(!startSet.equals(endSet)) {
    connectedComponents.remove(endSet);
    startSet.addAll(endSet);
    tree.addEdge(start, end, edge);
}

我现在不确定是否应该保留

!startSet.equals(endSet)

或者您是否想在修改后的代码中使用

startSet != endSet

。前一个版本使用“深度相等”进行测试（即考虑所涉及的集合的实际内容），而后一个版本仅通过对象标识工作，我认为如果您考虑

IdentityHashMap

路线，这会更合适。