必须并集的集合的Java结构？ (对于克鲁斯卡尔算法)

Question

我必须实现Kruskal's Algorithm在Java中。

我有一部分是按权重排序边缘，但是当我必须考虑保存每棵树的集合的结构时，我有点迷失了。

我想到有一个集合 vector ，其中每个集合代表一棵树。但如果我必须合并两棵树，我不知道该怎么办。从 vector 中删除两个元素并添加一个新的组合元素？

有没有一种结构可以让它变得更容易？

我需要的是:

• 迭代主集合中的所有集合
• 将一个元素添加到其中一个集合中，或者
• 创建一个新集合并将其添加到主要集合
• 合并其中两个集合(当然，删除它们的单个版本)

Answer 1

您在问题中链接到的维基百科文章中引用的不相交集数据结构是您需要的结构类型。我假设你有一个 Vertex类，并给出一个示例，说明 Java 中的“简单方法”可能是什么样子，使用 ArrayList<Vertex>表示形成连接组件的一组顶点。

您将修改您的 Vertex类看起来像

public class Vertex {

    // other data members
    private ArrayList<Vertex> component;

    public Vertex(/* arguments */) {
        // other initialization
        component = new ArrayList<>();
        component.add(this);
    }

    // other methods

    public ArrayList<Vertex> getComponent() {
        return component;
    }

    public void setComponent(ArrayList<Vertex> updatedComponent) {
        component = updatedComponent;
    }
}

这已经满足了涉及向集合添加元素的算法部分，因为构造函数负责创建新组件并将顶点添加到其自己的组件。

检查两个顶点是否 u和v位于您将使用的同一组件中

if (u.getComponent() == v.getComponent()) {
    // they are in the same component
} else {
    // the components are different
}

当你发现 u和v不在同一个组件中，您可以使用如下代码合并组件。

ArrayList<Vertex> larger;
ArrayList<Vertex> smaller;
if (u.getComponent().size() < v.getComponent().size()) {
    larger = v.getComponent();
    smaller = u.getComponent();
} else {
    larger = u.getComponent();
    smaller = v.getComponent();
}
for (Vertex aVtx : smaller) {
    aVtx.setComponent(larger);
}
larger.addAll(smaller);

我认为这就是正确实现 Kruskal 算法所需的全部内容，但我还没有解决您对主要集合的评论。如果您希望跟踪所有组件，以便可以看到它们在算法中任何点的样子，可以通过 HashSet<ArrayList<Vertex>> majorSet 来完成。 。当您构造每个顶点时，您可以将组件添加到 majorSet ，当您合并两个组件时，您将删除 smaller来自majorSet 。您可以迭代 majorSet.values()以标准方式。