[AL] Union-Find 알고리즘 - JavaScript

Union-Find 알고리즘은 간단하게 말하면 서로소 집합 (서로 중복되지 않고 공통 원소가 없는 부분 집합)을 표현할 때 사용하는 알고리즘이다. 주로 크루스칼 알고리즘 (Kruskal Algorithm)과 함께 사용된다.

Union-Find 알고리즘

Union-Find 알고리즘이란 위에서 말했던 것 처럼 서로소 집합을 표현할 때 사용하는 알고리즘이며,
주로 트리 (Tree) 구조를 이용하여 구현하게 된다.

과정

• makeSet(x)
  • x를 유일한 원소로 하는 새로운 집합을 생성
• unionSet(x,y)
  • x가 속한 집합과 y가 속한 집합을 합친다.
• findSet(x)
  • x가 어떤 집합에 속해있는지 찾는다.

구현 코드

// 그래프의 노드의 개수가 n개 일 때
// 자기 자신이 부모 노드로 존재하는 배열 생성
let parent = [];
for(let i=0; i<=n; i++) parent[i] = i;

// x가 어떤 집합에 속해있는지 재귀 함수를 이용해서 찾는다.
const getParent = (parent, x) => {
  if(parent[x] === x) return x;
  return parent[x] = getParent(parent, parent[x]);
}

// x와 y가 속한 집합(parent)을 찾아
// 둘중 더 작은 부모 값으로 합친다.
const unionParent = (parent, x, y) => {
  const s1 = getParent(parent,x);
  const s2 = getParent(parent,y);
  if(s1<s2) return parent[s2] = s1;
  else return parent[s1] = s2;
}

// x와 y가 속한 집합(parent)이 같은 부모를 갖는지 확인한다.
const findParent = (parent, x, y) => {
  const s1 = getParent(parent,x);
  const s2 = getParent(parent,y);
  if(s1===s2) return true;
  else return false;
}

참고 자료