Union-find 算法没有 return 预期结果

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()

我希望结果是

但是上面的算法returns

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

有没有人可以指出为什么会这样，以及我可以做些什么来获得预期的结果？

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()

输出

在无向图中将自边显示为边并不常见。

因此，而不是

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

通常指定顶点数。

Union-find 算法没有 return 预期结果

Union-find algorithm does not return expected result

python

graph-algorithm

union-find