python 구현 및 검색 집합

그리고 집합 은 이러한 데이터 구조 이다. 많은 데이터 가 있 고 일부 요 소 를 하나의 집합 에 두 고 다른 요 소 는 다른 집합 에 두 는 것 이다.
그것 의 조작 은 두 요소 가 하나의 집합 에 있 는 지, 두 요 소 를 합 쳤 는 지 확인 하 는 것 이다.합병 할 때 취 하 는 전략 은 다음 과 같다. 두 원소 가 있 는 집합의 모든 원 소 를 하나의 집합 에 함께 넣는다.
여기 서 두 개의 사전 을 사용 하여 집합 을 찾 습 니 다. 하나의 사전 은 현재 노드 의 부모 노드 정 보 를 저장 하고 다른 하 나 는 부모 노드 크기 를 유지 하 는 정 보 를 저장 합 니 다.

class UnionFindSet(object):
    """   """
    def __init__(self, data_list):
        """       ，          ，            
              ，           ，size  1"""
        self.father_dict = {}
        self.size_dict = {}

        for node in data_list:
            self.father_dict[node] = node
            self.size_dict[node] = 1

    def find_head(self, node):
        """             

                 ，               
                  
        """
        father = self.father_dict[node]
        if(node != father):
            father = self.find_head(father)
        self.father_dict[node] = father
        return father

    def is_same_set(self, node_a, node_b):
        """                """
        return self.find_head(node_a) == self.find_head(node_b)

    def union(self, node_a, node_b):
        """          """
        if node_a is None or node_b is None:
            return

        a_head = self.find_head(node_a)
        b_head = self.find_head(node_b)

        if(a_head != b_head):
            a_set_size = self.size_dict[a_head]
            b_set_size = self.size_dict[b_head]
            if(a_set_size >= b_set_size):
                self.father_dict[b_head] = a_head
                self.size_dict[a_head] = a_set_size + b_set_size
            else:
                self.father_dict[a_head] = b_head
                self.size_dict[b_head] = a_set_size + b_set_size

if __name__ == '__main__':
    a = [1,2,3,4,5]
    union_find_set = UnionFindSet(a)
    union_find_set.union(1,2)
    union_find_set.union(3,5)
    union_find_set.union(3,1)
    print(union_find_set.is_same_set(2,5))  # True
 

 
다음으로 전송:https://www.cnblogs.com/jiaxin359/p/9265208.html