联合查找算法未返回预期结果

Question

我使用this示例实现了以下联合发现算法：

import numpy as np


class UnionFind(object):

    def __init__(self, edges):
        self.edges = edges
        self.n_edges = np.max(edges) + 1
        self.data = list(range(self.n_edges))

    def find(self, i):
        if i != self.data[i]:
            self.data[i] = self.find(self.data[i])
        return self.data[i]

    def union(self, i, j):
        pi, pj = self.find(i), self.find(j)
        if pi != pj:
            self.data[pi] = pj

    def run(self):

        for i, j in self.edges:
            self.union(i, j)

        labels = dict()
        for i in range(self.n_edges):
            labels[i] = self.find(i)

        for k, v in labels.items():
            print(k, v)


if __name__ == '__main__':
    edges = [(1, 1), (2, 2), (2, 3), (3, 3), (4, 2), (4, 4)] // pairs of equivalent labels
    uf = UnionFind(edges)
    uf.run()

我希望结果是

0 0 
1 1
2 2
3 2
4 2

但是以上算法返回了

0 0 
1 1
2 3
3 3
4 3

也就是说，我希望最小的标签成为父标签

有人可以指出为什么会这样吗，我该怎么做才能获得预期的结果？

Answer 1

您想要Union-Find by Rank

代码

Source

class UF:
    """An implementation of union find data structure.
    It uses weighted quick union by rank with path compression.
    """

    def __init__(self, N):
        """Initialize an empty union find object with N items.

        Args:
            N: Number of items in the union find object.
        """

        self._id = list(range(N))
        self._count = N
        self._rank = [0] * N

    def find(self, p):
        """Find the set identifier for the item p."""

        id = self._id
        while p != id[p]:
            p = id[p] = id[id[p]]   # Path compression using halving.
        return p

    def count(self):
        """Return the number of items."""

        return self._count

    def connected(self, p, q):
        """Check if the items p and q are on the same set or not."""

        return self.find(p) == self.find(q)

    def union(self, p, q):
        """Combine sets containing p and q into a single set."""

        id = self._id
        rank = self._rank

        i = self.find(p)
        j = self.find(q)
        if i == j:
            return

        self._count -= 1
        if rank[i] < rank[j]:
            id[i] = j
        elif rank[i] > rank[j]:
            id[j] = i
        else:
            id[j] = i
            rank[i] += 1

    def __str__(self):
        """String representation of the union find object."""
        return " ".join([str(x) for x in self._id])

    def __repr__(self):
        """Representation of the union find object."""
        return "UF(" + str(self) + ")"

示例

使用示例边。

N = 5
edges = [(1, 1), (2, 2), (2, 3), (3, 3), (4, 2), (4, 4)] 

uf = UF(N)

for p, q in edges:
  uf.union(p, q)

uf.show()

输出

0 0
1 1
2 2
2 2
2 2

评论

通常不将自身边缘显示为无向图中的边缘。

因此，而不是

edges = [(1, 1), (2, 2), (2, 3), (3, 3), (4, 2), (4, 4)]

更常见的是拥有（即只是非自身的边缘）：

edges = [(2, 3), (4, 2)]

无论哪种情况，上述代码都会产生相同的输出。

由于未显示自边缘，所以无法从中获得顶点数量

self.n_edges = np.max(edges) + 1  # not normally correct 

通常指定顶点数。