목록분리 집합 (1)
고코딩
[자료구조] 분리집합(Disjoint set) 개념 및 JAVA 구현
Disjoint set? Disjoint set은 서로 중복되지 않는 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 교집합이 존재하지 않는 둘 이상의 집합을 말하고 데이터 집합을 다룰때 유용하게 쓰인다. 분리집합은 자식 노드가 부모 노드를 가리키는 형태이다. 또한 교집합입 없는 집합이기 때문에 차집합 연산이 있지 않다. 오직 Union-Find알고리즘을 사용하며 배열, 연결리스트, 비트벡터 등으로 이용하여 구현할수 있지만 구조는 트리구조를 가지게 된다. Union 연산 두개의 집합을 합한다. 각 집합의 부모 값을 얻어와 한쪽 부모가 다른쪽 부모를 가르키게 해 한개의 부모만 있는 집합을 만든다. 결국 한개의 집합에는 하나의 부모만을 가지게 된다. //N은 원소들을 넣은 배열 pub..
자료구조
2021. 1. 7. 15:55