방금 분해 된 세트 데이터 구조를 연구했고 "조합 찾기 데이터 구조"라고도하며 조합과 찾기가이 데이터 구조의 두 가지 주요 작업이라는 것을 알고 있습니다. 분리 된 세트에서 결합을 수행 할 수 있으며 마찬가지로 찾기 연산을 수행 할 수 있습니다. 저는 union과 find를 제외한 disjoint set에서 수행 할 수있는 다른 연산을 알고 싶습니다.분리 된 세트에서 수행 할 수있는 조작은 무엇입니까?
분리 세트 구조는 "공용 구조 찾기"라고도합니다. 따라서 union, find 및 MakeSet 작업을 지원해야합니다. 다른 작업은이 구조가 무엇인지에 관한 것이 아니며 지원 여부는 구현 및 목표에 달려 있습니다. 때로는 프로젝트의 추가 작업 요구에 맞게 특정 구현을 구체적으로 선택해야 할 수도 있습니다.
다른 기본 세트 관련 작업을 지원하면 좋을 것입니다. 그들을 열거하자 :
find입니다.바닐라 공용 구조체 찾기 데이터 구조를 사용하면 실제 집합을 열거 할 수 없으므로 많은 집합 연산을 사용할 수 없습니다. 이것은 바닐라 버전에서는 포인터가 한 방향으로 만 있기 때문입니다. 아래 그림에서 모든 대각선은 위쪽 화살표에 해당하고 루트 (위쪽 줄)는 집합의 루트 객체입니다.
o [set1] o [Set2]
/\ \
o o o
/
o
따라서 집합 1의 모든 개체를 찾을 방법이 없습니다. 예를 들어 루트 노드에서 경로를 추적 할 수 없습니다. 포인터도 아래쪽으로 가질 수 있지만 데이터 구조에 오브젝트가 임의의 수의 부모를 가질 수 있기 때문에 데이터 구조가 상당히 복잡해집니다.
그래서 다음과 같은 작업을 위해 정말 대부분의 :
이 정교한 동일한 세트에 속하는 것으로 간주되도록
union-find disjoint set 구조의 요점은 질문과 다른 응답자가 제안하는 것처럼 기본 설정 작업을 수행하는 것에 그다지 중요하지 않습니다. 대신 특정 알고리즘에 필요한 구조를 매우 효율적으로 구현하는 것입니다. 특히 연결된 구성 요소와 최소 스패닝 트리를 찾는 것이 가장 효율적인 구현을 union-find disjoint set 위에 구축합니다.