티스토리 뷰

Table of Contents


개요

프림 알고리즘

O(V^2) 알고리즘

O(V^2) 코드

O(E log V) 알고리즘

O(E log V) 코드

문제

프림 알고리즘의 정당성




1. 개요


 프림 알고리즘은 무향 연결 그래프가 주어질 때, '최소 스패닝 트리' 라고 부르는 서브 그래프를 찾는 알고리즘입니다. 크루스칼 알고리즘과 같은 용도이지만, 응용 상황에서 두 알고리즘의 효율성이 달라질 수 있기 때문에 둘 모두 알아두는 것이 좋습니다. 최소 스패닝 트리에 대한 개념을 모른다면 크루스칼 알고리즘을 먼저 보고 오시는 걸 추천합니다.




2. 프림 알고리즘


 프림 알고리즘은 MST를 찾기 위한 그리디 패러다임의 알고리즘입니다. 이 알고리즘을 따라가면 최소 스패닝 트리를 구할 수 있습니다.


step 0) 임의의 정점을 선택하여 비어있는 T에 포함시킨다. (이제 T는 노드가 한 개인 트리. )

step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

step 2) 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다. 

                (step 1에서 찾은 간선도 같이 T에 포함됩니다.)

step 3) 모든 노드가 T 에 포함될 때 까지, 1,2 를 반복한다.


 이 알고리즘을 통해 만들어진 최후의 T는 MST가 됩니다. 아래의 그래프에 프림 알고리즘을 순서대로 적용 시켜 보겠습니다. 편의 상, T에 포함된 노드는 빨간색, T에 아직 포함되지 않은 노드는 파란색으로 표시하겠습니다.



step 0) 임의의 정점을 선택하여 비어있는 T에 포함시킨다. (이제 T는 노드가 한 개인 트리. )

-> 초기 상태는 T에 아무것도 포함되어 있지 않습니다. 임의의 정점으로는 아무거나 선택해도 상관없지만, 예시에서는 1을 선택하겠습니다.



step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

-> 빨간색과 파란색을 연결하는 간선 중 가중치가 최소인 걸 찾으면 됩니다. 노드 1과 노드 3을 연결한 가중치 4의 간선이 최선입니다.


step 2) 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.

-> 노드 3을 T 에 포함시킵니다.



step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

-> 노드 2과 노드 3을 연결한 가중치 2의 간선이 최선입니다.


step 2)
 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.

-> 노드 2을 T 에 포함시킵니다.



step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

-> 노드 3과 노드 4을 연결한 가중치 6의 간선이 최선입니다.


step 2)
 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.

-> 노드 4을 T 에 포함시킵니다.



step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

-> 노드 4과 노드 5을 연결한 가중치 3의 간선이 최선입니다.


step 2)
 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.

-> 노드 5을 T 에 포함시킵니다.



step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

-> 노드 4과 노드 6을 연결한 가중치 8의 간선이 최선입니다.


step 2)
 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.

-> 노드 6을 T 에 포함시킵니다.



 이렇게 간선이 가중치의 합이 23인 트리가 완성되었으며, 이 트리가 그래프의 MST 입니다. 이러한 프림 알고리즘을 구현하는 데에는 2가지 방법이 있습니다.


 방법 1은 배열을 사용하여, T 와 각 노드를 연결하는 최소 간선 가중치를 찾는 방법이며 시간 복잡도는 O(V^2) 입니다.


 방법 2는 힙 ( min heap ) 을 사용해 최소의 간선 가중치를 찾는 방법이며, 시간 복잡도는 O(E log E), 즉, O(E log V) 입니다.


V = 정점의 개수, E = 간선의 개수




3. O(V^2) 알고리즘


 아래와 같은 두 배열을 잡으면 다익스트라와 비슷한 방식으로 프림 알고리즘을 구현할 수 있습니다.


dist [ i ] = T 에 들어간 노드 i 노드 사이의 간선 가중치 중 최소값

( 결국, T와 i 노드를 연결할 때 사용할 간선의 가중치입니다.)


selected[ i ] = i 노드가 T에 들어가 있으면 true, 아니면 false


 이 두 배열을 통해 프림 알고리즘을 구현해보겠습니다.


step 0) 임의의 정점을 선택하여 비어있는 T에 포함시킨다. (이제 T는 노드가 한 개인 트리. )

step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

step 2) 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.

step 3) 모든 노드가 T 에 포함될 때 까지, 1,2 를 반복한다.


step 0) 임의의 정점을 선택하여 비어있는 T에 포함시킨다. (이제 T는 노드가 한 개인 트리. )


1
2
3
4
5
for(int i=1; i<=pn; i++){ // 초기화
    dist[i] = INF;        // INF = 2140000000
    selected[pn] = false;
}
dist[1= 0;              // 1번 노드부터 선택
cs


 초기화 이후, dist[1] = 0 으로 만들어 주면, 이 후 자연스럽게 1번 정점이 T 에 포함되도록 할 수 있습니다.


step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.


 dist [ i ] = 'T에 있는 노드와 i 노드 사이의 간선 중 최소 가중치'가 있기 때문에, dist [ T에 없는 노드 ] 중 최소값을 찾으면 됩니다. 그러면 T 에 있는 노드와 T 에 없는 노드 사이의 최소 가중치와 같은 결과가 나오게 됩니다.


1
2
3
4
5
6
7
int now=-1, min_dist = INF;
for(int j=1; j<=pn; j++){
    if(!selected[j] && min_dist > dist[j]){
        min_dist = dist[j];
        now = j;
    }
}
cs


 이 구현에서는 어떤 노드와 연결된 간선 인지를 알기 위해 now 변수를 추가하였습니다.


step 2)
 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.


 어떤 노드인지는 step 1에서 이미 구했습니다. step1에서 구한 now를 포함 시키면 됩니다. 이 때, 노드 i 와 노드 now 사이에 간선이 있는 경우 dist [ i ] 를 갱신시켜야 합니다. now가 이제 T에 포함되었기에, (i, now) 간선의 가중치가 dist [ i ] 보다 작으면 dist [ i ] 를 바꿔줘야 하기 때문입니다.


1
2
3
4
ret+=min_dist; // 해당 간선의 가중치만큼, 최종 가중치를 더해준다.
selected[now] = true// T에 노드를 포함 시킨다.
for(auto edge: ad[now]) // T에 now 가 포함됨으로서 dist 배열도 한 차례 갱신해야 한다.
    dist[edge.first] = min(dist[edge.first], edge.second);
cs


step 3) 모든 노드가 T 에 포함될 때 까지, 1,2 를 반복한다.


 반복하면 됩니다.




4. O(V^2) 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//code by RiKang, weeklyps.com
#include <bits/stdc++.h>
#define PII pair<int,int>
 
using namespace std;
 
const int N = 1005, INF = 2140000000;
 
vector<PII> ad[N];  // ad[i] : i 노드가 출발지인 간선들, first = 목적지, second = 비용
int dist[N];        // dist[i] : 선택된 노드들과 i 노드가 연결되어 있는 간선의 비용 중 최소비용
bool selected[N];   // selected[i] : i 가 이전에 선택된 노드인가?
 
long long prim(int pn){
    long long ret = 0;
    for(int i=1; i<=pn; i++){ // 초기화
        dist[i] = INF;
        selected[pn] = false;
    }
    dist[1= 0;              // 1번 노드부터 선택
    for(int i=1; i<=pn; i++){
        int now=-1, min_dist = INF;
        for(int j=1; j<=pn; j++){
            if(!selected[j] && min_dist > dist[j]){
                min_dist = dist[j];
                now = j;
            }
        }
        if(now<0return (long long)INF; // 연결 그래프가 아님
        ret+=min_dist;
        selected[now] = true;
        for(auto edge: ad[now])
            dist[edge.first] = min(dist[edge.first], edge.second);
    }
    return ret;
}
 
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    while(m--){
        int v1,v2,c;
        scanf("%d %d %d",&v1,&v2,&c);
        ad[v1].push_back(PII(v2,c));
        ad[v2].push_back(PII(v1,c));
    }
    printf("%lld",prim(n));
    return 0;
}
cs




5. O(E log V) 알고리즘


 방법 1에서의 dist 배열을 버리고, 최소 힙을 이용하여 트리에 포함시킬 간선을 찾으면 O(E log V)가 가능합니다. 방법 변형은 다익스트라의 O(E log V) 방법과 유사합니다. T 안에 있는 노드가 출발점인 간선들을 모두 최소 힙에 넣어주면 됩니다.


dist = T 에 포함된 노드에서 출발하는 간선들을 넣은 최소 힙. ( 우선순위는 가중치, 목적지 순입니다. )


step 0)
 임의의 정점을 선택하여 비어있는 T에 포함시킨다. (이제 T는 노드가 한 개인 트리. )


1
2
3
4
for(int i=1; i<=pn; i++){ // 초기화
    selected[pn] = false;
}
dist.push(PII(0,1));
cs


초기화 이후, 최소 힙 dist에 (가중치 = 0, 목적지 = 1) 을 넣어주면, 이 후 자연스럽게 1번이 트리에 포함되도록 할 수 있습니다.

step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.


1
2
3
4
5
6
7
8
9
int now=-1, min_dist = INF;
while(!dist.empty()){
    now = dist.top().second;
    if(!selected[now]){
        min_dist = dist.top().first;
        break;
    }
    dist.pop();
}
cs


 (second 는 목적지 노드, first 는 가중치입니다.)

 dist.top()에 목적지 노드가 T 밖에 있는 간선이 있으면 그 간선을 선택하면 됩니다. dist에 저장된 간선들의 출발지 노드는 모두 T 안에 있고, 최소 힙이기 때문에 top에 있는 간선이 최선임은 당연합니다.


 반대로 목적지 노드가 T 안에 있다면, 간선에 있는 두 노드가 모두 T에 있는 것이므로 그냥 pop 을 해줘야 합니다. T 에 포함된 노드에서 출발하는 간선은 모두 dist 에 있기 때문에 이게 최선임을 증명할 수 있습니다.


step 2) 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.


1
2
3
ret+=min_dist;
selected[now] = true;
add_edge(now);
cs


 어떤 노드인지는 1에서 이미 구했습니다. now를 포함 시키면 됩니다. 또한 now 에서 출발하는 모든 간선을 dist 에 넣어주는 함수, add_edge(now) 만들어서 호출합니다.


1
2
3
4
5
void add_edge(int node){
    for(auto edge: ad[node]){
        dist.push(edge);
    }
}
cs


step 3) 모든 노드가 T 에 포함될 때 까지, 1,2 를 반복한다.


 반복하면 됩니다.




6. O(E log V) 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//code by RiKang, weeklyps.com
#include <bits/stdc++.h>
#define PII pair<int,int>
 
using namespace std;
 
const int N = 1005, INF = 2140000000;
 
vector<PII> ad[N];  // ad[i] : i 노드가 출발지인 간선들, first = 비용, second = 목적지
priority_queue<PII, vector<PII>, greater<PII> > dist;        // dist : 선택될 가능성이 있는 간선들
bool selected[N];   // selected[i] : i 가 이전에 선택된 노드인가?
 
void add_edge(int node){
    for(auto edge: ad[node]){
        dist.push(edge);
    }
}
 
long long prim(int pn){
    long long ret = 0;
    for(int i=1; i<=pn; i++){ // 초기화
        selected[pn] = false;
    }
    dist.push(PII(0,1));
    for(int i=1; i<=pn; i++){
        int now=-1, min_dist = INF;
        while(!dist.empty()){
            now = dist.top().second;
            if(!selected[now]){
                min_dist = dist.top().first;
                break;
            }
            dist.pop();
        }
        if(min_dist==INF) return (long long)INF; // 연결 그래프가 아님
        ret+=min_dist;
        selected[now] = true;
        add_edge(now);
    }
    return ret;
}
 
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    while(m--){
        int v1,v2,c;
        scanf("%d %d %d",&v1,&v2,&c);
        ad[v1].push_back(PII(c,v2));
        ad[v2].push_back(PII(c,v1));
    }
    printf("%lld",prim(n));
    return 0;
}
cs




7. 문제


(0) [BOJ 1922] 네트워크 연결


정답 코드는 위에 있으므로 생략




8. 프림 알고리즘의 정당성


 프림 알고리즘이 최소 스패닝 트리를 찾는다는 걸 증명해보도록 하겠습니다. 프림 알고리즘은 그리디 패러다임에 속하며 많은 그리디가 그렇듯이, 귀류법으로 증명 가능합니다. 크루스칼 증명과 대동소이합니다.


귀류법 ) 프림 알고리즘 결과가 MST 가 아니라고 해보겠습니다. ...(1)


T = 프림으로 선택된 간선들의 그래프


 위와 같이 T를 정의하면, 프림이 시작할 때 T에는 간선이 하나도 없습니다.

 프림이 진행됨에 따라, 간선이 하나씩 선택되면서 T에 포함되게 되지요.

 프림이 끝났을 때 T는 스패닝 트리이면서 최소 스패닝 트리는 아니게 될 것입니다.( (1)에 의해 프림 알고리즘의 결과가 MST가 아닌 경우를 이야기하고 있습니다.)


 이제 프림이 시작할 때의 T를 T-init, 프림이 끝났을 때의 T를 T-last라고 하면, 아래의 명제가 참이 됩니다.



 T-init은 공집합이기 때문에 MST의 부분 그래프였지만,

 T-last는 MST가 아닌 스패닝 트리이기 때문에 MST의 부분 그래프가 되는 것이 불가능합니다.


 따라서 프림 알고리즘상 선택된 순간, T가 MST의 부분 그래프가 되는 것이 불가능하도록 만든 간선 (u,v)가 존재해야 합니다. T는 간선의 삭제가 없고 추가만 있기 때문에, 이런 (u,v)가 존재해야 함을 증명할 수 있습니다.

 다시 말하면, 프림의 진행 과정 속에는 아래의 조건을 만족하는 T와 MST가 존재해야 합니다.



 이제 (u,v) 를 선택하기 직전의 T와, 그 T를 부분그래프로 가지는 MST 중 하나를 생각해 보겠습니다. ( (u,v) 이전의 프림 간선들을 모두 포함한 MST ) 그러면 MST 에서는 (u,v) 가 직접 연결되어 있지 않고 간접적으로 연결되어 있습니다. 그런데 MST 에서 u 와 v 를 연결하는 경로에는 T 안의 노드와 밖의 노드를 연결하는 간선이 무조건 포함되어야 합니다.


 왜냐하면 프림의 진행 과정 상 u 는 T 에 포함되어 있고 v 는 T 에 포함되어 있지 않기 때문입니다. 이제 u와 v를 연결하는 경로 상에 있으면서 T 안의 노드와 밖의 노드를 연결하는 간선 중 하나를 삭제하고 (u,v) 를 추가하면 스패닝 트리가 유지되면서 코스트는 MST 이하인 트리가 완성됩니다.


 삭제한 간선의 코스트 >= (u,v) 코스트 이며,

( *  (u,v)의 가중치는 T 안의 노드와 밖의 노드를 연결하는 모든 간선 중 최소입니다. 그렇지 않다면 (u,v) 가 프림 알고리즘에서 선택될 수 없습니다.)


 삭제한 간선의 두 정점도 (u,v) 를 경유하면 연결되기 때문에 스패닝 트리도 유지되기 때문입니다. 그런데, 코스트가 MST 이하인 트리도 MST 일 수 밖에 없습니다.


결국, (u,v) 를 포함한 MST 를 찾았습니다. 이 결과를 거슬러 올라가면 (1) 에 모순입니다.


※ 본문의 코드들은 C++ 14 환경으로 작성되었습니다.



'그래프 ( Graph )' 카테고리의 다른 글

프림 알고리즘 ( Prim's algorithm )  (4) 2017.11.28
트리의 지름  (1) 2017.11.25
크루스칼 알고리즘 ( Kruskal's algorithm )  (0) 2017.11.23
유니온 파인드 ( Union-find )  (0) 2017.11.21