서로소집합

[알고리즘] 유니온-파인드 (Union-Find) (자바 Java)

목차 유니온 파인드 (Union-Find) 서로소 집합(Disjoint-sets) 서로 중복 포함된 원소가 없는 집합들 → 교집합이 없다 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분, 이를 대표자(representative)라고 함 연산 Make-Set(x): 원소 x로만 구성된 집합을 만든다 Find-Set(x): 원소 x를 가진 집합을 알아낸다 Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다 표현 방법 연결 리스트, 트리 1. 연결 리스트 같은 집합의 원소들은 하나의 연결리스트로 관리 연결리스트의 맨 앞의 원소를 집합의 대표원소로 삼음 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다 2. 트리 하나의 집합을 하나의 트리로 표현 자식 노드가 부모노드를 ..