[알고리즘/그래프] 합집합 찾기(Union-Find)

합집합 찾기(Union Find) 알고리즘이란?

---

대표적인 그래프 알고리즘으로, 여러개의 노드가 존재하는 경우 두 개의 노드를 선택하여 선택된 노드가 서로 같은 그래프에 속하는지 확인하는 알고리즘이다.

 

• 서로소 집합(Disjoint-Set) 알고리즘이라고도 불리운다.
• 크루스칼 알고리즘(Kruskal Algorithm)등 고급 그래프 알고리즘에 사용된다.
• 사이클(Cycle)이 있는지 확인하는 문제

구현 방법

1. 노드의 부모가 자기 자신이 되도록 초기화한다.
2. 두개의 노드를 연결한다. 이 때 더 작은 노드가 부모가 되도록 합친다. -- unionFind
3. 재귀를 사용하여 두개의 노드가 같은 그래프에 속해있는지 확인한다. -- findParent

알고리즘 구현

// 부모노드를 찾는다.
const getParent = (parent, x) => {
  if (parent[x] === x) return x;
  return (parent[x] = getParent(parent, parent[x]));
};

// 두 부모 노드를 합친다.
const unionParent = (parent, a, b) => {
  a = getParent(parent, a);
  b = getParent(parent, b);
  if (a < b) {
    parent[b] = a;
  } else {
    parent[a] = b;
  }
};

// 같은 부모를 가지는지(같은 그래프에 속해있는지) 확인한다.
const findParent = (parent, a, b) => {
  a = getParent(parent, a);
  b = getParent(parent, b);
  return a === b ? 1 : 0;
};

구현 코드

// 1. 자기 자신이 부모가 되도록 초기화한다.
let parent = [];

for (let i = 0; i <= 10; i++) {
  parent[i] = i;
}

// 2. 노드를 연결한다.
unionParent(parent, 1, 2);
unionParent(parent, 2, 3);
unionParent(parent, 3, 4);
unionParent(parent, 5, 6);
unionParent(parent, 6, 7);
unionParent(parent, 7, 8);

// 3. 3과 4가 연결되어있는지 확인한다.
findParent(parent, 3, 4);