Union-Find 알고리즘(서로소 집합 알고리즘)

*Union-Find 알고리즘

- Disjoint-Set(서로소 집합) 알고리즘이라고 불린다. 

- 지금 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 검사하는 알고리즘.

- 간선의 양끝 정점이 서로 다른 집합에 속하는 경우, 두 정점을 연결하여도 사이클이 형성되지 않는다.

- Kruskal MST 알고리즘을 구현하는데 사용된다.

#include <stdio.h>

#define MAX_VERTICES 100

int parent[MAX_VERTICES];    // 부모 노드

int num[MAX_VERTICES];       // 각 집합의 크기

// 초기화

void set_init(int n) {

    int i;

    for (i = 0; i < n; i++) {

        parent[i] = -1;

        num[i] = 1;

    }

}

 

// vertex가 속하는 집합을 반환한다.

int set_find(int vertex) {

    int p, s, i = -1;

    for (i = vertex; (p = parent[i]) >= 0; i = p) {   // 루트 노드까지 반복

        s = i;     // 집합의 대표 원소

    }

    for (i = vertex; (p = parent[i]) >= 0; i = p) {

        parent[i] = s;    // 집합의 모든 원소들의 부모를 p로 설정

    }

    return s;

}

 

// 두개의 원소가 속한 집합을 합친다.

void set_union(int s1, int s2) {

    if (num[s1] < num[s2]) {

        parent[s1] = s2;

        num[s2] += num[s1];

    }

    else {

        parent[s2] = s1;

        num[s1] += num[s2];

    }

}