[22-03-10] 학습일지 - 유니온 파인드(Union-Find)

들어가기에 앞서

상호 배타적 집합 (Disjoint Set)

- 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조직하는 자료 구조

- 공통 원소가 없는 부분 집합들로 나누어진 원소들에 대한 자료구조

- 서로소 집합 자료구조

 

유니온 파인드

- 그래프 알고리즘, 합집합 찾기의 의미를 가짐

- 상호 배타적 집합 이라고도 한다.

- 여러 노드가 존재할 때 두 개의 노드를 선택하여 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘

- 유니온과 파인드 크게 3가지 연산으로 이루어져 있습니다.

 

> Make-Set : 초기화, x를 유일한 원소로 하는 새 집합을 생성

> Union 연산 :  x가 어떤 집합에 포함되어 있는지 찾는 연산

> Find 연산 : x와 y가 포함되어 있는 집합을 합치는 연산

 

 

 

유니온 파인드 어디에 사용하는 걸까?

- 전체 집합을 구성 원소들이 겹치지 않도록 분할하는 데 자주 사용

- Krusakl MST 알고리즘 에서 새로 추가할 간선이 사이클을 형성하는지 판단

 

 

C언어로 구현한 유니온 파인드

int root[MAX_SIZE];
int rank[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++) {
  root[i] = i;
  rank[i] = 0;
}


int find(int x) {
  if (root[x] == x) {
      return x;
  } else {
      return root[x] = find(root[x]);
  }
}


void union(int x, int y){
   x = find(x);
   y = find(y);

   if(x == y)
     return;

   if(rank[x] < rank[y]) {
     root[x] = y;
   } else {
     root[y] = x;

     if(rank[x] == rank[y])
       rank[x]++;
   }
}

 

참고 및 소스코드 블로그

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog