[Algorithm] 최소 신장 트리 (Minimum Spanning Tree, MST)

날짜:


최소 신장 트리 (Minimum Spanning Tree, MST)

신장 트리, 또는 스패닝 트리는 그래프에서 모든 정점을 사이클이 생기지 않게 간선으로 연결하는 것을 말하며, 이 때 간선의 가중치의 합이 최소가 되는 것을 최소 신장 트리라고 부른다. '최소' 라는 이름 때문에 MST는 단 1개만 존재할 것 같지만 보장할 수 없다. 가중치의 합이 최소로 같은 그래프가 다른 모양으로 만들어질 수도 있기 때문이다. 

위의 그래프에서 붉은 선이 간선인 스패닝 트리일 때, 두 그래프 모두 같은 가중치의 합을 가지는 최소 스패닝 트리가 된다.
최소 스패닝 트리, MST를 구하는 알고리즘은 크루스칼 알고리즘 (Kruskal's Algorithm)과 프림 알고리즘 (Prim's Algorithm)이 많이 알려져 있다.




1. 크루스칼 알고리즘 (Kruskal's Algorithm)

 모든 간선에 대해 가중치가 가장 작은 간선부터 연결을 하면서 MST를 만드는 것이다. 이 때, 간선을 연결하는 과정에서 사이클이 생기면 해당 간선은 가중치가 작더라도 연결을 끊어버린다. (사실 그냥 연결을 안해버리는 것이다.) 아래와 같은 그래프가 존재할 때, 이 그래프의 MST를 구해보자.
(검은색 간선은 연결이 일어나지 않은 간선, 파란색 간선은 연결 확인 중인 간선, 붉은색 간선은 연결 완료 된 간선이다.)



1) 위의 그래프 중 가장 작은 가중치를 가지는 간선 1을 연결시켜 준다.
2) 해당 간선으로 인해 생기는 사이클이 존재하지 않으므로 연결을 완료해 준다. 이제 가중치가 2인 간선 2개를 연결해주자.
3) 이 때 2개의 간선을 모두 연결하면 가중치 1 - 2 - 2 로 사이클이 생기게 되므로 둘 다 연결할 수 없다. 왼쪽 2만 연결하도록 하자. 연결이 완료 됐으면 이제 가중치가 3인 간선을 확인해보자.

 4) 사이클이 생기지 않으므로 완료한 후, 가중치가 4인 간선을 연결해보자.
5) 이 때, 오른쪽 위의 간선은 사이클이 생기지 않지만, 왼쪽 아래의 간선은 3 - 4 - 1의 사이클이 생긴다. 따라서 오른쪽 위의 간선만 연결해주면 되겠다.
6) 이렇게 모든 정점이 연결이 완료 되었고, 이 그래프는 최소 스패닝 트리가 된다.





2. 프림 알고리즘 (Prim's Algorithm)

임의의 시작 정점을 정해서 이 점과 연결 된 정점들로부터 가중치가 최소인 간선을 찾아 연결해서 확장시켜 나가는 방법이다. 이 때 크루스칼 알고리즘과 마찬가지로 어떤 간선의 연결로 인해 사이클이 생기면 연결을 끊어준다. (역시 연결을 애당초 안해준다.) 위에서 사용한 그래프를 재활용해서 알아보자.


1) 프림 알고리즘에서의 시작 정점을 어떤 점을 기준으로 해도 최소 스패닝 트리를 만들 수 있다. 편의상 가장 위의 정점을 시작 정점 0으로 설정해준다. 시작 정점 0과 연결 된 정점은 그림과 같이 각각 7, 4의 값을 가지게 된다.
2) 위에서 구한 시작 정점에서 최소 간선인 4와 연결 된 정점에 값 4를 저장해주고, 해당 정점과 연결해 준다. 이번엔 탐색을 4에서 시작했으므로 4와 인접한 정점에 각각 1, 2, 5를 적어준다.
3) 탐색 정점 1에서 시작 정점으로 가는 7, 아래로 내려가는 2가 존재한다. 이 때 시작 정점으로 가는 간선은 사이클이 형성됨과 동시에 0 < 7이므로 업데이트하지 않고, 따라서 아래로 내려가게 될 것이다. 

4) 2에서 연결 된 정점에서 정점 4로는 사이클이 형성되서 갈 수 없고, 오른쪽 정점은 기존의 정점 값 5 > 2에서 연결 된 간선 3 이므로 값도 3으로 업데이트 될 것이다. 아래 방향은 값 4로 저장된다.


5) 정점 3에서 위의 정점은 사이클이 형성됨과 동시에 5 > 4이므로 업데이트 하지 않고, 아래의 정점은 간선 1 < 정점 4이므로 1로 업데이트 된다.

6) 모든 정점이 사이클 없이 연결 되었으며 MST가 형성된다.



Kruskal Algorithm과 Prim Algorithm에 대해 알았다면 이제 어떻게 구현하는지도 알아야한다. 어떤 알고리즘을 익히는데 가장 좋은 방법은 문제를 풀고 틀리면서 깨닫는 것이라 생각한다.
따라서 [백준] 1197. 최소 스패닝 트리를 이용하여 구현하는 법을 알아보자.


문제

https://www.acmicpc.net/problem/1197




풀이 - Kruskal Algorithm

kruskal algorithm은 Union-Find 알고리즘과 같은 방식으로 동작한다. Union-Find의 시간 복잡도는 O(Elog E)보다 빠르므로 크루스칼 알고리즘의 시간복잡도는 O(ElogE)다.

더 자세히 말하자면 Union-Find 알고리즘에서 Find는 O(logN)이, Union은 Find의 영향을 받으므로 O(logN)의 시간복잡도가 나오게 된다. 이 때 Find는 호출마다 수행시간이 변하기 때문에 정확한 시간 복잡도는 O(a(N))이라는 시간이 나오며, 이 때 a는 아커만 함수로 사실상 상수 시간을 가지는 형태로 나온다. 따라서 크루스칼 알고리즘의 시간복잡도는 사실상 Sort함수의 시간에 영향을 받으며, Sort는 O(ElogE)이므로 크루스칼 알고리즘도 O(ElogE)가 나오게 된다.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// kruskal 정점을 정의한다.
typedef struct kruskal{
    int from, to, val;
}ks;

int parent[100002], answer;
ks edge[100002];


bool operator<(const ks& a, const ks& b){
    return a.val < b.val;
}

// 정점의 조상을 찾는다. (가장 위에 있는 부모)
int find(int u){
    // 만약 현재 정점의 부모가 자기 자신이라면 그냥 자신을 리턴해준다.
    if(u == parent[u]) return u;
    // 재귀로 해당 정점의 조상을 찾아준다.
    return parent[u] = find(parent[u]);
}

// 합치고자 하는 점 2개, 즉 시작점과 끝점을 연결해준다.
void merge(int u, int v){
    
    // 시작점과 끝점의 부모를 찾아준다.
    u = find(u); v = find(v);
    // 시작점의 부모를 끝점으로 세팅해준다.
    parent[u] = v;
}

int main(){
    
    int v, e, a, b, c; cin >> v >> e;
    for(int i = 1; i <= v; i++){
        parent[i] = i;
    }
    // 간선에 대한 정보를 만들어 준다.
    for(int i = 0; i < e; i++){
        ks k;
        cin >> a >> b >> c; k.from = a; k.to = b; k.val = c;
        edge[i] = { a, b, c };
    }
    // 간선은 가중치가 가장 작은 것부터 탐색해야 하므로 오름차순 정렬해준다. 이 때, 위에서 정의한 연산자 오버로딩에 의해 정렬된다.
    sort(edge, edge + e);

    int cnt = 0, i = 0;
    // 간선은 최대 v - 1개 까지 나올 수 있는데, MST에서 2개의 정점 사이를 연결하는 간선은 1개뿐이다.
    while(cnt != v - 1){
        // 시작 정점과 끝 정점의 부모가 같지 않을 때 ==> 사이클이 형성되지 않을 때
        if(find(edge[i].from) != find(edge[i].to)){
            // 시작 정점의 부모를 끝 정점의 부모로 세팅해준다. 간선의 개수를 1개 늘려준다. 이 간선의 가중치를 answer에 더해준다.
            merge(edge[i].from, edge[i].to); cnt++; answer += edge[i].val;
        }
        // 다음 정점으로 이동해준다.
        i++;
    }
    cout << answer;
    return 0;
}



풀이 - Prim Algorithm

프림 알고리즘은 우선순위 큐에 넣고, 여기에 있는 정점을 빼서 확인하므로 우선순위 큐의 삽입 및 정렬 시간에 영향을 받는다. 따라서 프림 알고리즘은 O(ElogV) 시간을 갖는다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 프림 알고리즘은 현재 정점에서 인접한 곳의 정점의 값을 변경시키면서 확장시키는 방식이다. 따라서 현재 정점을 방문해서 인접한 정점의 값이 바뀐 적이
// 있다면 더 이상 해당 정점에서는 탐색할 필요가 없다.

int visited[100001], answer;
vector<pair<int, int> > p[100001];

void prim(int start){
    
    // 시작 정점은 탐색 완료 처리해준다.
    visited[start] = 1;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    
    // 시작 정점과 연결된 인접한 정점들을 모두 우선순위 큐에 넣어준다.
    // 가중치, 정점 순으로 넣어준다. 우선순위큐는 first의 크기 순으로 먼저 비교하고, 그 다음에 second순으로 비교하기 때문에 가중치를 앞에 둔 것.
    // 따라서 우선순위큐에서 꺼낸 정점은 start 노드와 연결된 특정 노드 중 가중치가 가장 작은 간선을 가진 정점이 된다.
    for(int i = 0; i < p[start].size(); i++){
        int next = p[start][i].first, nextv = p[start][i].second;
        pq.push(pair<int, int>(nextv, next));
    }
    
    while(!pq.empty()){
        // 가중치가 currv인 간선을 가진 curr번 정점
        int curr = pq.top().second, currv = pq.top().first; pq.pop();
        // 이 정점이 탐색한 적이 있으면 탐색을 하지 않는다.
        if(visited[curr] == 1) continue;
        // 탐색한 적이 없으면 탐색하며 가중치는 answer에 더해준다.
        visited[curr] = 1;
        answer += currv;
        
        for(int i = 0; i < p[curr].size(); i++){
            // 다시 현재 정점과 인접한 정점들과, 현재 정점과 연결된 정점의 가중치를 묶어서 우선순위 큐에 넣어준다.
            int next = p[curr][i].first, nextv = p[curr][i].second;
            pq.push(pair<int, int>(nextv, next));
        }
    }

    cout << answer;
}

int main(){
    
    int v, e; cin >> v >> e;
    for(int i = 0; i < e; i++){
        int a, b, c; cin >> a >> b >> c;
        p[a].push_back(pair<int, int>(b, c));
        p[b].push_back(pair<int, int>(a, c));
    }
    prim(1);
    return 0;
}

크루스칼 알고리즘이 O(ElogE) 시간을, 프림 알고리즘이 O(ElogV) 시간을 갖는다. 따라서 간선의 개수가 적으면 크루스칼 알고리즘을, 간선의 개수가 적으면 프림 알고리즘을 쓰는게 효율적이라고 볼 수 있다.

댓글

댓글 쓰기