union_find.md

Union find

• disjoint-set 이란?
• union-find 구현

Disjoint-Set 이란?

• 서로소 또는 상호베타 집합들은 서로 중복 포함된 원소가 없는 집합들이다. => 교집합이 없다.
• 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. 이를 대표자라고 한다.
• 상호베타 집합을 표현하는 방법
  • 연결 리스트
  • 트리 (효율적)
• 상호베타 집합 연산
  • make-set(x) : [초기화 단계], 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산
  • find-set(x) : [대표자 찾기], x를 포함하는 집합을 찾는 오퍼레이션
  • union-set(x,y) : [합치기], x와 y를 포함하는 두 집합을 통합하는 오퍼레이션

Union-find 구현

const makeSet = arr => arr.fill().map((_,i) => i);

const findSet = (arr, x) => arr[x] === x ? x : arr[x] = findSet(arr[x]);

const unionSet = (arr, x, y) => {
    x = findSet(arr, x);
    y = findSet(arr, y);
    if (x === y) return ;
    arr[y] = x;
}

let arr = Array(8);
arr = makeSet(arr);
console.log(arr)

// group 1
unionSet(arr,2,0);
unionSet(arr,2,1);

// group 2
unionSet(arr,4,3);
unionSet(arr,4,6);
unionSet(arr,4,7);
unionSet(arr,5,4);

// group 1 + group 2
unionSet(arr,5,2);

console.log(arr)

/**
 * [ 0, 1, 2, 3, 4, 5, 6, 7 ]
 * [ 2, 2, 5, 4, 5, 5, 4, 4 ]
 */