분리 집합 (Disjoint Set)
글 작성자: NoHack
728x90
Disjoint Set 🙂
분리 집합(Disjoint Set)은 교집합을 갖지 않는 집합들을 의미합니다. 각 집합은 트리로도 표현이 가능한데, 다만 이 경우에는 자식 노드들이 부모를 가리키는 형태로 구현해야 합니다. 그렇게 하나의 트리를 집합과 같은 개념으로 보면 되고, 연결 관계가 없는 트리끼리 서로 분리 집합이라 보면 됩니다. 분리 집합은 합집합 말고는 연산이 따로 없기 때문에 구현은 쉽지만, 그래프 이론에서 많이 사용되므로 잘 알아 두고 넘어가야 합니다.
집합 생성
function Set(data) {
this.data = data;
this.parent = null;
}
const set1 = new Set(1);
const set2 = new Set(2);
집합은 부모만 알면 되기 때문에, 트리에서의 노드와 다르게 부모에 대한 멤버 변수만 갖습니다.
집합 탐색
const findSet = (set) => {
while (set.parent !== null) {
set = set.parent;
}
return set;
};
집합을 합치기 위해서는 해당 집합이 소속되어 있는 부모 집합을 알아야 합니다.
합집합 (집합 합치기)
const unionSet = (set1, set2) => {
set2 = findSet(set2);
set2.parent = set1;
};
합집합은 그룹이 다른 두 집합을 같은 그룹으로 만드는 작업이며, 분리 집합 구조에 유일하게 존재하는 기능입니다. 이 함수는 set2를 set1의 집합에 포함시킨다 가정하고, set2의 부모를 먼저 탐색합니다. 그렇게 set2의 최상위 부모 집합을 찾게 되면, 최상위 부모 집합의 parent를 set1으로 할당하여 집합을 합치게 됩니다.
References 📝
본문의 내용은 GeeksforGeeks의 Disjoint Set 자료를 참고해 작성했습니다 ❤️
'💻 컴퓨터공학 > 자료구조' 카테고리의 다른 글
우선순위 큐 (Priority Queue) (0) | 2021.10.30 |
---|---|
힙 (Heap) (0) | 2021.10.29 |
수식 트리 (Expression Tree) (0) | 2021.10.26 |
이진 트리 (Binary Tree) (0) | 2021.10.26 |
LCRS 트리 (LCRS Tree) (0) | 2021.10.25 |
댓글
이 글 공유하기
다른 글
-
우선순위 큐 (Priority Queue)
우선순위 큐 (Priority Queue)
2021.10.30 -
힙 (Heap)
힙 (Heap)
2021.10.29 -
수식 트리 (Expression Tree)
수식 트리 (Expression Tree)
2021.10.26 -
이진 트리 (Binary Tree)
이진 트리 (Binary Tree)
2021.10.26