1

FIND-SET(x) – 返回代表或指向包含元素 x 的集合代表的指针。

在算法中，find-set(x) 用于不相交的数据结构。我不明白这个功能的用途。假设我有一个包含 4 个顶点 a、b、c、d 的图，权重为 ab=4, bc=5, cd=6 ... find-set(u)!=find-set(v ) （其中 u,v 是图中的任何顶点）帮助我定义图中循环的出现！？？查找定义为：

function Find(x)
     if x.parent == x
        return x
     else
        return Find(x.parent)
4

1 回答 1

2

Find-Set(x)在不相交的数据结构中最常用于实现最小生成树（MST）。

如果u和v在同一个集合中，则表示它们已经连接。如果它们已经连接，则在它们之间添加另一个连接会创建一个循环。

我们可以通过说所有顶点都在它们自己不同的单元素集中来开始分析这一点。当我们在两个顶点之间建立连接时，例如a-b，然后我们将a和b放在同一个集合中。因此，我们需要确定它们如何在同一个集合中；因此，我们Find-Set(x)用来确定它们是否在同一个集合中（在您的情况下，这是一个不相交的森林实现）。

您提供的示例没有循环，因此我将添加另一个边：

例子

最初，假设我们有一组顶点a、b和。我们想要确定最小生成树，以便将所有三个顶点连接到同一个森林的最小边数。cd

现在可用的边缘： (a, b), (c, d), (b, c), (d, c)（额外的边缘是一个循环！）

这假设您知道顶点、边和森林的定义，它们都是基本的图术语

由于a和b目前是不同的集合，我们可以通过一种算法将它们组合起来，例如Merge-Set(a, b)将它们放在同一个集合中：A=(a, b)虽然仍然存在c并且d必须连接。注意这里A是集合的名称

我们可以看到这(c, d)也是可能的；所以，我们可以合并它们：B=(c, d)我们也有(a, b). B是这个不相交集的名称

现在我们可以合并A=(a, b)并且B=(c, d)知道我们有 edge (b, c)。由于集合内有多个元素，我们首先通过 判断边是否必要Find-Set(x)。如果Find-Set(b) == Find-Set(c)那么我们知道我们有一个循环，即 if A == B。幸运的是，我们没有，因为(b, c)不会出现在 setA=(a, b)或B=(c, d). 现在我们像往常一样合并它们并到达我们的 MST，它是一个集合：（A=(a, b, c, d)注意 B 已被删除！）。

回想一下我们的额外优势，它现在是一个循环。如果我们尝试相加(d, c)，我们会看到 whichd和c驻留的集合是相同的 ieFind-Set(d) == Find-Set(c)或A == Asinced并且c都在 set 中A。因此，我们可以确定这条边创建了一个循环！

于 2012-05-09T17:23:33.140 回答