MST - 프림(Prim), 크루스칼(Kruskal) 알고리즘

MST 는 Minimum Spanning tree 인데 용어를 간략히 정리하자면 

스패닝 트리 : 그래프에서 일부 간선을 선택해 만든 트리

최소 스패닝 트리: 스패닝 트리 중에 선택한 간선의 가중치의 합이 최소인 트리  (트리의 정의 : 정점이 N개라면 간선은 N-1개인 경우 )

MST를 구현하는 방법에는 크게 3가지로 나누어 볼 수 있는데

1) 프림 (Prim)  - 정점을 중심으로 

2) 크루스칼 (Kruskal)  - 간선을 중심으로 

3) 솔린 알고리즘 (sollin's algorithm)

으로 나누어 볼 수 있다. 근데 보통은 같은 시작 복잡도를 가지고 있으므로 간단한 크루스칼을 많이 사용하는것 같다. 해당 포스팅에서는 크루스칼까지만 언급을 하도록 하겠다. 

먼저 프림(Prim algorithm)의 경우

1. 그래프에서 임의의 한 지점을 선택한다.

2. 선택한 정점과 선택하지 않은 정점을 연결하는 간선중에 최소값을 구한다. (u,v라고 표현한다면 u는 선택한 정점 , v는 선택하지 않은 정점)

3. 선택한 간선을 MST에 추가하고, v를 선택한다.

4. 모든 정점을 선택하지 않았다면 2번으로 돌아가서 반복한다. 

해당과 같은 그림이 있다면 임의의 한 정점을 선택하고 그 점을 기점으로 시작하는 것이다. (그림에서는 1을 선택한 모습)

그렇다면 프림의 시간복잡도는 어떻게 될까?? 

각각의 정점에 대하여 모든 간선들을 살펴 본게 되므로 시간복잡도는 O(V*E) 이며 최대 O(N^3)이라고 한다 . 

구현의 경우에는 2번 과정에서 '연결하는 간선중에 최소값을 구한다' 라고 적혀있기 때문에 매번 최소값을 찾을때 효율적인 ..  Priority_queue를 사용한다.

    for(int i=0;i<line;i++){
        int a,b,c;
        scanf("%d %d %d" , &a, &b, &c);
        arr[a].push_back(make_pair(b,c));
        arr[b].push_back(make_pair(a,c));
    }
    
    check[1] = true;
    priority_queue<pair<int,int>> q;
    
    for (auto &p : arr[1]) {            //arr[1]에 있는 모든 pair형을 다 반복한다.
        q.push(make_pair(-p.second,p.first));
    }
    
    int answer =0;
    
    while(q.empty() != 1){
        auto p = q.top();               //auto로 인하여 p가 자동적으로 Pair형이 된다.
        q.pop();
        if(check[p.second] == true){    //끝점이 방문된적이 있다면 그 경우는 스킵한다.
            continue;
        }
        check[p.second] = true;
        answer += -p.first;
        int x = p.second;
        for (auto &p : arr[x]) {         //연결되는 모든 점의 간선들을 다 넣어준다.
            q.push(make_pair(-p.second,p.first));
        }
    }
    
    printf("%d\n" , answer);

이렇게 Priority_queue를 사용하게 되면 최소값을 LogE만에 찾을 수 있으므로 시간복잡도가 O(VlogE) ?? O(ElogE)?? 가 된다. 

이번에는 크루스칼(Kruskal) 알고리즘에 대해 알아보자. 프림이 정점을 주로 봤다면 크루스칼은 간선에 집중한다.

크루스칼의 핵심은 가중치가 작은 E부터 먼저 살펴본다는 점이다.  (해당 부분은 http://kks227.blog.me/220791837179 님의 블로그를 참조하였습니다. 갓 the 블로그)

1. 간선들을 가중치 순으로 오름차순 정렬하고 정점들의 각 컴포넌트를 초기화 한다.

2. 간선들을 훓으면서 양쪽 정점을 포함한 컴포넌트가 연결되어 있지 않으면 간선을 뽑고 , 연결한다. 

3. 간선 V-1개가 뽑히는 순간 MST 완성. 즉 종료 

영문 위키에 있는 예제를 보도록 하자.

그림이 크다. 하지만 잘 알아볼 수 있을 것이다 ㅋㅋㅋ..... 

해당 방식으로 구현을 하게된다면 그리디(Greedy) 측면으로도 볼 수 있을것이고 , V-1번째로 뽑힌 간선의 가중치가 바로 MST를 이루는 간선중 가장 큰 가중치를 가지게 되는 경우이다. 

int find(int x){
    if(x == parent[x]){
        return x;
    }else{
        return parent[x] = find(parent[x]);
    }
}
void Union(int x,int y){
    x = find(x);
    y = find(y);
    parent[x] = y;
}
 

for (int i=1; i<=num; i++) {
    parent[i] = i;
}
 
vector<pair<int,pair<int,int>>> arr;
 
for (int i=0; i<line; i++) {
    int a,b,c;
    scanf("%d %d %d" , &a,&b,&c);
    arr.push_back(make_pair(c,make_pair(a,b)));     //가장 앞에는 가중치 second에는 출발,끝
}
 
sort(arr.begin(),arr.end());                        //정렬
 
long long int answer = 0;
 
for(int i=0;i<line;i++){
    auto p = arr[i];
    int x = find(p.second.first);
    int y = find(p.second.second);
    if (x != y) {                                   //두 부모가 다르면
        Union(p.second.first, p.second.second);     //합쳐준다.
        answer += p.first;
    }
}
 

와 같이 코딩할 수 있다. 

여기서 주의할점 !!! 마지막 for문에서 보통 반복을( i=1;i<=line ;i++) 처럼 1부터 시작하는 경우가 있는데.... 0부터 시작이다 !!