1. Disjoint Set Union Find Naive

Disjoint Set or Union Find implementation¶

References:¶

1. https://www.techiedelight.com/disjoint-set-data-structure-union-find-algorithm/
2. https://www.geeksforgeeks.org/disjoint-set-data-structures/
3. https://www.youtube.com/watch?v=eTaWFhPXPz4&ab_channel=TECHDOSE
4. https://www.youtube.com/watch?v=ayW5B2W9hfo&t=8s&ab_channel=PotatoCoders
5. https://www.youtube.com/watch?v=ibjEGG7ylHk&ab_channel=WilliamFiset

In [7]:

class DisjointSetNaive:
    def __init__(self):
        self.parent = {}

    def make_set(self, universe):
        """
        # create 'n' disjoint sets for each of the items
        # here every element initially is pointing to itself
        # so each element is a parent of itself

        parent = { 1:1, 2:2, 3:3...}

        """

        for i in universe:
            self.parent[i] = i

    def find(self, k):
        """
        consider below array for example

        Node:    1  2  3
        Parent: [1, 1, 2]

        the recursion will continue until the
        representative element of the set is found
        """
        if self.parent[k] == k:
            return k
        return self.find(self.parent[k])

    def union(self, x, y):

        x_root = self.find(x)
        y_root = self.find(y)

        self.parent[x_root] = y_root

    def print_set(self, universe):
        print(self.parent)
        print([self.find(i) for i in universe])

class DisjointSetNaive: def __init__(self): self.parent = {} def make_set(self, universe): """ # create 'n' disjoint sets for each of the items # here every element initially is pointing to itself # so each element is a parent of itself parent = { 1:1, 2:2, 3:3...} """ for i in universe: self.parent[i] = i def find(self, k): """ consider below array for example Node: 1 2 3 Parent: [1, 1, 2] the recursion will continue until the representative element of the set is found """ if self.parent[k] == k: return k return self.find(self.parent[k]) def union(self, x, y): x_root = self.find(x) y_root = self.find(y) self.parent[x_root] = y_root def print_set(self, universe): print(self.parent) print([self.find(i) for i in universe])

In [8]:

universe = [0, 1, 2, 3, 4, 5]

universe = [0, 1, 2, 3, 4, 5]

In [9]:

ds = DisjointSetNaive()

ds = DisjointSetNaive()

In [10]:

ds.make_set(universe)
ds.print_set(universe)

ds.make_set(universe) ds.print_set(universe)

{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5}
[0, 1, 2, 3, 4, 5]

In [11]:

ds.union(4, 3)
ds.print_set(universe)

ds.union(4, 3) ds.print_set(universe)

{0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 5}
[0, 1, 2, 3, 3, 5]

In [12]:

ds.union(4, 5)
ds.print_set(universe)

ds.union(4, 5) ds.print_set(universe)

{0: 0, 1: 1, 2: 2, 3: 5, 4: 3, 5: 5}
[0, 1, 2, 5, 5, 5]