Реализация непересекающихся множеств в Python

Я относительно новичок в Python. Я изучаю непересекающиеся множества и реализовал его следующим образом:

class DisjointSet:
    def __init__(self, vertices, parent):
        self.vertices = vertices
        self.parent = parent

    def find(self, item):
        if self.parent[item] == item:
            return item
        else:
            return self.find(self.parent[item])

    def union(self, set1, set2):
        self.parent[set1] = set2

Теперь в коде драйвера:

def main():
    vertices = ['a', 'b', 'c', 'd', 'e', 'h', 'i']
    parent = {}

    for v in vertices:
        parent[v] = v

    ds = DisjointSet(vertices, parent)
    print("Print all vertices in genesis: ")
    ds.union('b', 'd')

    ds.union('h', 'b')
    print(ds.find('h')) # prints d (OK)
    ds.union('h', 'i')
    print(ds.find('i')) # prints i (expecting d)

main()

Итак, сначала я инициализировал все узлы как отдельные непересекающиеся множества. Затем объединяются bd и hb, что составляет набор: hbd, затем объединяется hi, что должно (как я предполагал) дать нам набор: ihbd. Я понимаю, что из-за установки родителя в этой строке union(set1, set2):

self.parent[set1] = set2

Я устанавливаю родителя h как i и, таким образом, удаляю его из набора bd. Как я могу получить набор ihbd, где порядок параметров в union() не будет давать разные результаты?


python-3.x algorithm data-structures disjoint-sets
person Abrar    schedule 04.01.2019    source источник
comment
Вы не должны использовать аргумент parent в конструкторе, поскольку у вызывающей стороны нет выбора, что указать. Вы должны заполнить его в init вместо main()   -  person Matt Timmermans    schedule 04.01.2019
comment
Вот реализация Py: nayuki.io/res/disjoint-set -data-structure/disjointset.py. Еще один: github.com/mrapacz/disjoint-set   -  person Abhijit Sarkar    schedule 23.12.2019

Ответы (2)


arrow_upward
10
arrow_downward

Ваша программа работает неправильно, потому что вы неправильно поняли алгоритм реализации непересекающихся множеств. Объединение реализуется путем изменения родительского узла root, а не узла, предоставленного в качестве входных данных. Как вы уже заметили, слепая модификация родителей любого узла, который вы получаете на входе, просто уничтожит предыдущие объединения.

Вот правильная реализация:

def union(self, set1, set2):
    root1 = self.find(set1)
    root2 = self.find(set2)
    self.parent[root1] = root2

Я бы также посоветовал прочитать Структура данных с непересекающимся набором для получения дополнительной информации, а также возможных оптимизаций.

person merlyn    schedule 04.01.2019

arrow_upward
1
arrow_downward

Чтобы ускорить реализацию, вы можете обновить родителя по мере того, как вы find()

    def find(self, item):
        if self.parent[item] == item:
            return item
        else:
            res = self.find(self.parent[item])
            self.parent[item] = res
            return res
person HK Tong    schedule 20.12.2020