파이썬에서 분리 된 포리스트 설정하기

Question

파이썬에서 분리 시스템을 구현하고 있지만 벽에 부딪혔다. 나는 시스템을위한 트리 구현을 사용하고 시스템의 Find(), Merge() 및 Create() 함수를 구현하고있다.

효율성을 위해 순위 시스템과 경로 압축을 구현하고 있습니다.

캐치 (catch)는 이러한 함수가 매개 변수로 분리 된 세트를 취해야하므로 통과가 어려워집니다.

class Node(object): 
    def __init__(self, value): 
     self.parent = self 
     self.value = value 
     self.rank = 0 

def Create(values): 
    l = [Node(value) for value in values] 
    return l 

만들기 기능은 값 목록을 가져 와서 적절한 데이터가 포함 된 단일 노드 목록을 반환합니다.

나는

def Merge(set, value1, value2): 
    value1Root = Find(set, value1) 
    value2Root = Find(set, value2) 
    if value1Root == value2Root: 
     return 
    if value1Root.rank < value2Root.rank: 
     value1Root.parent = value2Root 
    elif value1Root.rank > value2Root.rank: 
     value2Root.parent = value1Root 
    else: 
     value2Root.parent = value1Root 
     value1Root.rank += 1 

, 병합 기능이 비슷하게 생각하고 있지만 나는 노드와의 목록을 취할 필요가 있기 때문에 찾기() 함수를 구현하는 방법을 잘 모르겠어요 값 (노드가 아님)을 매개 변수로 사용합니다. 찾기 (설정, 값)가 프로토 타입이됩니다.

노드가 Find (x)에 대한 매개 변수로 사용되는 경우 경로 압축을 구현하는 방법을 알고 있지만이 방법으로 인해 문제가 발생합니다.

도움을 주시면 감사하겠습니다. 고맙습니다.

설명을 위해 편집 됨.

Answer 1

분명히 노드 쌍에 merge 함수를 적용해야합니다.

그래서 find 기능은 단일 노드 매개 변수를 사용하고 다음과 같아야합니다

def find(node): 
    if node.parent != node: 
     node.parent = find(node.parent) 
    return node.parent 

또한

파이썬 쉽게 번역입니다 wikipedia has pseudocode.

Answer 2

이 데이터 구조의 구현은 작업 union과 find가 개별 집합이 아닌 분리 된 집합 포리스트 클래스의 메서드로 구현 될 수 있다는 것을 알게되면 더 간단 해집니다.

C++을 읽을 수 있다면 my take on the data structure을 살펴보십시오. 외부 세계의 실제 세트를 숨겨 API의 숫자 인덱스로만 나타냅니다. 파이썬에서, 그것은

class DisjSets(object): 
    def __init__(self, n): 
     self._parent = range(n) 
     self._rank = [0] * n 

    def find(self, i): 
     if self._parent[i] == i: 
      return i 
     else: 
      self._parent[i] = self.find(self._parent[i]) 
      return self._parent[i] 

    def union(self, i, j): 
     root_i = self.find(i) 
     root_j = self.find(j) 
     if root_i != root_j: 
      if self._rank[root_i] < self._rank[root_j]: 
       self._parent[root_i] = root_j 
      elif self._rank[root_i] > self._rank[root_j]: 
       self._parent[root_j] = root_i 
      else: 
       self._parent[root_i] = root_j 
       self._rank[root_j] += 1 

같은 것 (테스트하지 않습니다.)

이 경로를 따라하지 않을 경우, 코드의 클라이언트가 실제로 Node들과 Find 필수의 지식을 가지고해야합니다 Node 인수를 취하십시오.

Answer 3

찾기는 항상 항목에서 수행됩니다. 찾기 (항목)는 항목이 속한 집합을 반환하는 것으로 정의됩니다. 합병은 노드를 가져 가면 안되며 병합에는 항상 두 개의 항목/세트가 필요합니다. Merge 또는 union (item1, item2)은 먼저 각각 (item1)과 find (item2)를 찾아서 각각이 속한 집합을 반환해야합니다. 그 후 위쪽 트리로 표시되는 작은 세트를 키에 추가해야합니다. 찾기가 실행되면 항상 경로를 되돌아가 압축합니다.

경로 압축을 사용하여 테스트 한 구현은 here입니다.