0

我必须在 Java中实现Kruskal 算法。

我有一部分是按重量排序边缘，但是当我不得不考虑保存每棵树的集合的结构时，我有点迷茫。

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

有没有一种结构可以使它更容易？

我需要的是：

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

1 回答 1

1

您在问题中链接到的维基百科文章中引用的不相交集数据结构是您需要的结构类型。我假设您Vertex的实现中有一个类，并举例说明 Java 中的“简单方法”可能是什么样子，使用 anArrayList<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()。

于 2015-09-26T05:32:17.373 回答