Algorithm - Union-find

Union-find

• 대표적인 그래프 알고리즘
• 합집합 알고리즘 또는 서로소(Disjoin-Set) 알고리즘이라고도 부름
• 주로 트리(Tree) 구조를 이용하여 구현됨
• 크루스칼(Kruskal) 알고리즘과 함께 사용됨
  • 크루스칼 알고리즘 : 그래프 내의 모든 노드들을 가장 적은 비용으로 연결하기 위해 사용되는 알고리즘

methods of Union-find Algorithm

• getParent(parent, x)
  • x의 부모 노드를 반환하는 메서드
  • 본인 노드 x가 나올 때까지 재귀적으로 호출함
• unionParent(parnet, a, b)
  • a와 b 노드의 부모 노드를 합치는 메서드
  • a와 b 노드의 부모 노드를 비교하여 더 작은 값을 가진 부모 노드로 합침
• findParent(parent, a, b)
  - a와 b 노드가 서로 같은 그래프에 속하는지 판별하는 메서드

function getParent(parent, x) {
  if (parent[x] === x) return x;
  return parent[x] = getParent(parent, parent[x]);
}

function unionParent(parent, a, b) {
  a = getParent(parent, a);
  b = getParent(parent, b);
  a < b ? parent[b] = a : parent[a] = b;
}

function findParent(parent, a, b) {
  a = getParent(parent, a);
  b = getParent(parent, b);
  return a === b;
}

// 그래프의 노드 개수가 10개일 때, 자기 자신을 부모 노드로 갖는 배열 생성
const parent = [];
for (let i = 1; i <= 10; i++) {
  parent[i] = i;
}

// 1-2-3-4, 5-6-7-8
unionParent(parent, 1, 2);
unionParent(parent, 2, 3);
unionParent(parent, 3, 4);
unionParent(parent, 5, 6);
unionParent(parent, 6, 7);
unionParent(parent, 7, 8);
console.log('1과 5는 같은 그래프에 존재한다', findParent(parent, 1, 5));
unionParent(parent, 1, 5);
console.log('1과 5는 같은 그래프에 존재한다', findParent(parent, 1, 5));

참고

• Union-Find - 안경잡이 개발자 블로그