algorithm - 联合查找算法如何与 "real"数据一起使用

Question

在普林斯顿算法类(class)的开头，介绍了动态连接问题(快速查找、快速联合)。这是它的描述方式:

The input is a sequence of pairs of integers, where each integer represents an object of some type and we are to interpret the pair p q as meaning “p is connected to q.” We assume that “is connected to” is an equivalence relation, which means that it is

• Reflexive : p is connected to p.
• Symmetric : If p is connected to q, then q is connected to p.
• Transitive : If p is connected to q and q is connected to r, then p is connected to r.

它有一个名为quick-find的简单实现:

One approach is to maintain the invariant that p and q are connected if and only if id[p] is equal to id[q]. In other words, all sites in a component must have the same value in id[].This method is called quick-find because find(p) just returns id[p], which immediately implies that connected(p, q) reduces to just the test id[p] == id[q] and returns true if and only if p and q are in the same component...To combine the two components into one, we have to make all of the id[] entries corresponding to both sets of sites the same value, as shown in the example at right.

我的问题是如何将其用于真实对象？它适用于整数，但如果我需要知道对象 A 是否连接到对象 B，而不是 3 是否连接到5？我能想到的一个解决方案是拥有一个对象数组，其中每个对象在数组中的索引对应于用于连接的数组的索引。例如:

   1   2   3   4   5
[ { } { } {A} { } {B} ]   <---- real data

   1   2   3   4   5
[  1   2   3   4   3 ]    <---- connections (3 and 5 have the same group id 3)

是这样应用的吗？

Answer 1

您的建议肯定会奏效，但当对象列表以某种方式发生变化(例如以不同方式排序)时可能会变得麻烦。

您可以通过使用提到的 id 属性(或任何其他名称)扩展您的对象来实现提到的 quick-find 方法。

例如，如果您有这些对象(使用 Python 语法):

a = { "num":  1, "code": "test" };
b = { "num": 15, "code": "house" };
c = { "num":  9, "code": "garden" };
d = { "num":  4, "code": "flower" };
e = { "num": 24, "code": "cat" };

然后将 id 属性添加到这些对象(这种扩展的语法在许多语言中都不同):

a["id"] = 1 # extend the object with an additional property.
b["id"] = 2
c["id"] = 3
d["id"] = 4
e["id"] = 3

然后创建一个函数，告诉您两个对象是否已连接，如 quick-find 中所述:

def are_connected(x, y):
    return x["id"] == y["id"];

在这种情况下，以下测试的结果为真:

print (are_connected(c, e)); # True

备选方案:保持连接独立

如果您不想通过添加 id 属性来改变您的原始对象，您可以创建一个单独的 map 。有些语言可以为每个对象提供一个唯一的标识符。例如，在 Python 中，可以使用内置的 id() 函数检索此标识符。如果不可用，您将使用对象的唯一属性，该属性在示例数据中为 num 属性。所以在 Python 中:

conn = {}
conn[id(a)] = 1
conn[id(b)] = 2
conn[id(c)] = 3
conn[id(d)] = 4
conn[id(e)] = 3

def are_connected(x, y):
    return conn[id(x)] == conn[id(y)];

print (are_connected(c, e)); # True

快速联合算法

在这种方法中，您不会(总是)为连接的对象存储相同的 id，而是让它们指向同一组连接对象中的另一个(子到父)，该树的根指向它自己.

如果需要测试两个对象是否连接，您将找到它们各自连接到的两个根(通过遍历它们的祖先到树的顶部)并查看它们是否共享该根。

使用一些不同的示例数据，并使用 id 属性，它看起来像这样:

a = { "num":  1, "code": "test" };
b = { "num": 15, "code": "house" };
c = { "num":  9, "code": "garden" };
d = { "num":  4, "code": "flower" };
e = { "num": 24, "code": "cat" };
f = { "num": 88, "code": "dog" };

然后将 id 属性添加到这些对象(这种扩展的语法在许多语言中都不同):

a["id"] = a # it is a root, so a self-reference
b["id"] = a # same group as a
c["id"] = c # root of different tree
d["id"] = c # same group as c
e["id"] = c # same group as c
f["id"] = d # same group as c, but child of d

可以这样表示:

           a             c
           |            / \
           b           d   e
                      /
                     f

告诉您两个对象是否连接的函数现在看起来像这样:

def are_connected(x, y):
    while x["id"] != x: # while not at the root
        x = x["id"] # go upward in tree
    while y["id"] != y: # same for y
        y = y["id"] # go upward in tree
    return x == y; # if root is the same: the original objects are connected

请注意，您也可以将其编写为递归函数。

在这种情况下，以下测试的结果为真:

print (are_connected(e, f)); # True