유니온-파인드(Union-Find),연결판정

 

크루스칼 알고리즘을 정리하려고 했는데 
유니온-파인드 구조를 모르면 크루스칼에서 연결판정을 지을 수 없으므로 해당 구조부터 설명함.

위와 같은 형태로 각 부분 별 정점이 묶여있다고 하자.
그러면 

총 4개의 집합으로 정점들이 묶여 있다. 그런데 여기서 집합을 연결하는데 이게 연결이 이미 되어 있는지 안되어 있는지 연결판정을 지어야 하는데 1-2를 먼저 연결하고 7-8을 어떻게 판정을 할 것이냐? 라는 문제가 발생함.

그래서 이것들의 집합을 대표하는 정점을 기준으로 묶어 준다고 보면, 낮은 정점이 기준이라 하면

 

 

이런 식으로 묶여 있는 형태가 된다. 
이때 정점 1-2를 연결하면 

 

 

이런 꼴이 되는 거다. 그리고서 정점 2를 연결을 대표하는 것은 정점 1이 된다.

그러면 7과 8이 연결하려고 했을 때 
7번과 8번의 정점을 대표하는 정점이 다르면 ? 연결할 수 있고 
대표하는 정점이 같으면 ? 연결하면 사이클이 된다는 의미가 됨!

 

이 그림에서 7-8은 연결할 수 없다는 것이 판정이 되는 거다.

그러면 
이 내용을 코드로

 

int vertex_root[]; // 정점의 루트를 저장
int find(int sub); // 루트가 뭔지 알아야 판정을 지을 수 있으므로 루트를 찾는 함수
bool isUnion(int u, int v); // 두 정점이 연결이 되어 있는지 확인하는 함수
int union_find(int u, int v); // 정점u 정점v 가 연결이 되어있지 않다면 연결하는 함수

 

함수를 3개 정도 만들면 될 것 같다. 
주석으로 적어두긴 했는데
0) vertex_root[] 정점 루트 저장!
1) find 루트찾기
2) isUnion 합쳐져있음?
3) union_find 보고 합치자!
이 4개를 이용해서 구현하면 된다.
초깃값으로 0) vertex_root[] 를 모두 -1로 설정하고 시작하거나,

정점 0은 없다치고 0으로 설정하면 그건 코드 작성하는 사람 마음일 것 같다. 보통 책에서는 음수로 설정해두자 라고 하긴하던데..

그러면... 코드를 작성하면.. 아래 일 것 같은데.. 집합의 크기를 따져야하는데 아래는 따지지 않았으니... 효율이진 못...

 

#include<cstdio>
#include<vector>
using namespace std;
 
typedef vector<int> VI;
 
VI vertex_root;
 
int find(int sub){
    if(vertex_root[sub]==-1){ // 루트 초기 값을 -1로 지정, -1이라면? 자기자신이 루트
        return sub;
    }else{
        return find(vertex_root[sub]);
    }
}
 
bool isUnion(int u, int v){
    return find(u) == find(v);
}
 
bool union_find(int u, int v){
    if( !isUnion(u, v) ){
        int root_u = find(u);
        int root_v = find(v);
        // 더 작은 정점을 기준하여 루트로 세움.
        if(root_u < root_v) vertex_root[root_v] = root_u;
        else if(root_u > root_v) vertex_root[root_u] = root_v;
        return true;
    }
    return false;
}