Реализация несвязного множества в Python - PullRequest
Новая
       54

Реализация несвязного множества в Python

0 голосов
/ 04 января 2019

Я относительно новичок в 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() не даст других результатов?

1 Ответ

0 голосов
/ 04 января 2019

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

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

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

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

...