최소 스패닝 트리 알고리즘

kasterra·2021년 3월 25일

핵심 자료구조 - 그래프

목록 보기

8/8

최소 스패닝 트리

이번 포스팅 에서는, 최소 스패닝 트리를 만드는 알고리즘에 관해서 알아보겠습니다. 우선 도입에 앞서서, 최소 스패닝 트리 라는 것의 정의부터 짚고 넘어 가는것이 순서에 맞겠지요.

스패닝 트리는 신장 트리라고도 불리며, 간단하게 설명하면, 그래프의 간선 일부분을 사용해서, 사이클 없이 그래프의 정점을 잇는 그래프 입니다. 사이클이 없는 그래프이기 때문에, "트리"라고 부를 수 있습니다. 스패닝 트리의 조건만 만족되면, 스패닝 트리라고 할 수 있기 때문에, 한 그래프에 여러개의 스패닝 트리가 존재할 가능성 또한 있습니다.

최소 스패닝 트리는, 스패닝 트리의 "간선의 가중치의 합"이 최소가 되는 스패닝 트리를 말합니다. 물론, 최소 스패닝 트리도 여러개일 수 있습니다. 줄여서 MST(Minimum Spanning Tree)라고도 합니다.

최소 스패닝 트리의 개념이 알고리즘 대회에 자주 출제되는 편은 아니라고 하나, 그래프 관련 문제를 풀 때, 최소 스패닝 트리를 구하는 알고리즘의 원리를 응용해서 풀 수 있는 문제가 나올수도 있기 때문에 이 글에서 다루어 보고자 합니다. 그리고, 둘다 그리디 알고리즘이기 때문에, 알고리즘을 머리속에 받아드리는데에 뭔가 많은 노력이 필요하지 않습니다.

크루스칼 알고리즘

크루스칼 알고리즘은 되게 직관적이고 그리디한 방법을 사용해서 그래프의 최소 스패닝 트리를 찾아내는 알고리즘 입니다. 모든 간선의 합이 최소가 된다는 최소 스패닝 트리에는 가중치가 큰 간선보다는, 가중치가 작은 간선들이 많을 것이니, 가중치가 작은 간선들 위주로 스패닝 트리를 만들면 되지 않겠느냐 하는 아이디어에서 출발하는 알고리즘 입니다.

개념

크루스칼 알고리즘은, 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 이후, 가장 작은 가중치를 가진 간선부터 차례차례 트리에 추가합니다. 트리이기 때문에, 해당 간선을 트리에 추가한 결과물이 사이클이 생겨서, 트리라고 부를 수 없게 되버리면 그 간선은 추가하지 않고, 다음 간선 추가를 시도합니다.

자료구조의 선택

위에서 개념을 설명할 때, 매 간선의 추가를 진행할 때 마다, 해당 간선을 추가했을 때, 사이클이 생기는지 여부를 확인한다고 하였습니다. 사이클이 있는지 확인하는 방법은, 전에 DFS를 다뤘던 글에서, 다뤘던 내용대로, 깊이 우선 탐색을 실행한 후, 역방향 간선이 있는지 확인하는 식으로 확인이 가능하긴 합니다. 하지만 이 방법은 각 간선마다 깊이우선 탐색을 하기 때문에, DFS의 시간복잡도인 $O(|V|+|E|)$ 에서 $|E|$ 를 곱해서, $O(|E|^2)$ 가 됩니다. 이것보다 좀 더 빠른 방법이 있었으면 좋겠다 라는 생각이 드는 시간이 걸리는군요.

해답은 존재합니다. 전에 적었던 포스팅 중에서 union-find 라는 자료구조를 소개한 글이 있습니다. union-find 자료구조는 임의의 한 원소를 대상으로, 어떤 집합에 속해 있는지 거의 상수시간안에 알려주는 자료구조 입니다. 이를 이용하면 $O(|E|)$ 시간에 이를 해낼 수 있+습니다. 간선 $(u,v)$ 를 추가한다고 합시다. 만약, 정점 $u$ 와 $v$ 가 같은 컴포넌트 안에 속해있다면, 간선 $(u,v)$ 를 현재 생성중인 트리에 집어 넣는 행동이, 사이클을 만드는 결과를 불러 일으키게 될것 입니다.

구현

이제 실제 구현이 어떻게 되는지 알아보겠습니다. union-find 자료구조에 해당하는 DisjointSet의 구현은 위의 블로그 포스팅을 참조해 주시기 바랍니다. Shift키를 누르고 링크를 누르면 새 창에서, ctrl 키를 누르고 링크를 누르시면 새 탭에서 클릭한 링크의 글을 보실 수 있습니다.

struct DisjointSet;//union-find 자료구조
const int MAX_V = 100;
int V;//정점의 개수
vector<pair<int,int> >adj [MAX_V];

int kruskal(vector<pair<int,int> >& selected) {
    int ret = 0;
    selected.clear();
    vector<pair<int,pair<int,int> > > edges;
    for(int u = 0; u < V; ++u)
        for(int i = 0; i < adj[u].size(); ++i){
            int v = adj[u][i].fist, cost = adj[u][i].second;
            edges.push_back(make_pair(cost,make_pair(u,v)));
        }
    sort(edges.begin(),edges.end());//비용 순으로 오름차순 정렬
        
    DisjointSet sets(V);
    for(int i = 0; i < edges.size(); ++i) {
        int cost = edges[i].first;
        int u = edges[i].second.first, v = edges[i].second.second;
        if(sets.find(u) == sets.find(v)) continue;//사이클이 생기면 안넣는다
        sets.merge(u,v);
        selected.push_back(make_pair(u,v));
        ret += cost;
    }
    return ret;
}

시간 복잡도는, for문이 $O(|E|)$ 이고, 정렬에서 $O(|E|lg|E|)$ 이므로, 전체 시간복잡도는 $O(|E|lg|E|)$ 라고 보면 되겠습니다.

증명

크루스칼 알고리즘은 그리디 알고리즘이기 때문에, 작동이 어떻게 되는지는 쉽게 알 수 있습니다만, 이 알고리즘의 정당성은 그리디 알고리즘의 특성상 반드시 확인하고 가야 합니다.

그리디 알고리즘을 증명하는 방법은

탐욕적 속성(greedy choice property) 증명 : 탐욕적 선택을 했을 때, 손해를 보는 경우가 없다는것을 증명한다. 이 경우에는, 탐욕적으로 간선을 골랐을 때, 간선의 가중치의 합이 더 불어나지는 않는다 라는것을 증명하면 된다.
최적 부분구조(optimal substructure) 증명 : 문제의 최적해가, 부분 문제들에 대해서도 최적해여야 한다. 부분 문제들의 최적해를 모아서, 전체 문제의 해를 만들기 때문.

최적 부분구조가 성립함을 알아봅시다. 원래 그래프의 간선의 일부를 사용하여 MST를 하나 만들었다고 합시다. 거기에 정점 하나를, 가장 비용이 저렴하면서, 사이클을 만들지 않는 간선 하나로 기존의 MST와 연결해서 트리를 연장했을 때, 그것 역시 스패닝 트리이고, 비용이 가장 저렴한 간선으로 연결해서 트리를 만들었으므로, 그것 역시 MST라고 할 수 있겠네요. 그런식으로 그래프의 모든 정점을 포함하는 MST를 만들면, 원래 문제 해결이지요.

이게 어떻게 크루스칼 알고리즘에 쓰이는지 간단히 살펴보겠습니다. 크루스칼 알고리즘이 작동하는 과정을 그림으로 그려보면, 트리가 듬성듬성 여러개 생겼다가, 작은 트리들이 점점 커지며, 하나의 큰 트리로 만들어 지면서 알고리즘이 마쳐지는 그러한 그림인 경우가 많습니다.
그 작은 부분트리들은, 크루스칼 알고리즘에 의해 가중치가 작은 간선들 순서대로 연결되었으니, 그 트리를 구성하고 있는 정점들의 MST로 볼 수 있습니다.
이제 부분 트리들이 서로 합쳐지는 과정을 생각해 봅시다. 부분 트리중에 한개만 트리의 형태로 남기고, 나머지 트리들을 하나의 간선으로 압축해서 보자면 위에서 설명했던 최적 부분구조에 대한 설명을 적용할 수 있습니다. 부분 트리 하나에 새로운 부분 트리를 연결하는것을, 좀 크기가 큰 정점을 연결하는것으로 보는 것이지요. 만약에, 정점 하나만 연결하는 상황이면, 좀 큰 정점이 아닌, 그냥 정점을 연결하는 것이니 크게 다를 것 없지요.

탐욕적 속성에 관한 증명 또한 간단하게 해낼 수 있습니다. 크루스칼 알고리즘이 선택하는 간선 중, 그래프의 MST에 포함되어 있지 않은 간선들이 있다고 합니다. 그중 첫번째로 선택되는 간선을 $(u,v)$ 라고 합시다. MST는 이 간선을 포함하지 않지만, MST의 정의 상, $u$ 와 $v$ 를 연결하는 간선이 분명히 존재합니다. 곰곰히 생각해보면 한가지를 알 수 있는데, MST에서 $u$ 와 $v$ 를 연결하는 간선 중 하나는, 반드시 $(u,v)$ 보다 가중치가 같거나 커야 합니다. 만약 모든 간선의 가중치가 $(u,v)$ 보다 작다면, 그리디 알고리즘인 크루스칼 알고리즘이, 짧은 간선들 냅두고 가중치가 큰 $(u,v)$ 를 선택할 이유가 없기 때문이죠. $(u,v)$ 를 포함하지 않는 MST에서, u와 v를 연결하는 간선 중 가중치가 $(u,v)$ 보다 같거나 큰거 하나 골라서 끊어버리고, $(u,v)$ 를 연결하면, 사이클이 생기지 않으면서(기존에 u와 v를 연결하던 간선들중 하나가 삭제되어, u와 v가 같은 컴포넌트에 속해있지 않음), 또 다른 MST를 형성할 수 있게 해주므로, 크루스칼 알고리즘은 정당하다 라고 말 할수 있습니다.

프림 알고리즘

크루스칼 알고리즘은 전체 그래프에서 짧은 간선들을 순서대로 모아서 MST를 만듭니다. 즉, 정점에 붙어있는 간선들의 가중치가 작은 순서대로 트리에 추가하는 방식으로 MST를 만듭니다.

반면 프림 알고리즘은 크루스칼 알고리즘보다, BFS에 좀 더 닮아 있습니다. 정점들을 탐색하면서, 해당 정점에 인접한 간선 중, 사이클을 만들지 않는 가장 길이가 작은 간선을 트리에 추가해서, 최소 스패닝 트리를 만들어 나가는 알고리즘 입니다. 크루스칼 알고리즘과는 다르게, 프림 알고리즘이 동작하는 과정은, 작은 스패닝 트리가 확장되가는 모습으로 보이는 특징이 있습니다.

개념

프림 알고리즘은 시작점 하나에서 부터 출발 합니다. 시작점 하나를 트리에 넣습니다. 트리에 있는 정점들에 인접한 간선들 중에서 비용이 가장 싸고, 그러면서도 사이클을 만들지 않는 간선을 찾아서, 그 간선과, 그 간선에 연결되어 있는 정점을 트리에 추가합니다. 이 과정을 모든 정점이 트리에 포함될때까지 반복해주면 끝입니다.

최적화

개념이 이토록 간단한 만큼, 구현도 그만큼 간단한게 프림 알고리즘입니다. 앞에서 설명한 제약사항들만 빠르게 검사될 수 있도록 구현하면 됩니다. 간선이 트리에 포함되어 있는지를 added[]라는 배열을 만들어서 관리하고, 가장 싼 간선은 하나 하나 순회하면서 찾으면 되지만, 그렇게 된다면, 정점을 하나 추가한다고 간선들을 찾는데 $O(|E|)$ 의 시간이 걸리고, 이를 $|V|$ 번 반복해야 하므로, 시간복잡도는 $O(|V||E|)$ 가 되는데, 위에서 설명한 크루스칼의 $O(|E|lg|E|)$ 보다 별로라서, 실용성이 그닥 없어 보입니다.

이를 최적화 하는데 필요한 아이디어 하나는, 한 정점에 연결되는 간선이 두개 이상인경우, 그 간선들을 매번 하나 하나 검사하는것이 시간 낭비임을 깨닫는 것입니다. 한 정점에 가중치가 다른 간선이 여러개 꽃혀 있다해도, 어짜피 한번 검사할 때, 필요로 하는 것은 "가장 작은 가중치" 입니다. 그리고 새로운 정점을 트리에 등록할 때, 한 점을 두번 등록하는 일이 없음을 생각한다면, 모든 정점에 대해서, 연결되어 있는 가장 작은 가중치의 간선에 대한 정보를 저장해 놓으면, 이를 통해서, 연결할 간선을 찾는 작업을 $O(|E|)$ 가 아닌, $O(|V|)$ 만큼의 시간에 할 수 있고, 따라서, 총 시간 복잡도는 가장 작은 가중치를 알아보는 과정인 $O(|E|)$ 를 고려하면, $O(|V|^2+|E|)$ 임을 알 수 있지요.

구현

아래는 위에서 설명한 사항들을 구현하는 코드입니다. 이 코드에서, 간선에 대한 정보를 정확하게 알기 위해서, 간선의 다른 한쪽 끝을 저장하는 parent[]가 있음을 인지하면서 아래의 코드를 읽어 주세요.

const int MAX_V = 100;
const int INF = 987654321;
int V;
vector<pair<int,int> > adj[MAX_V];

int prim(vector<pair<int,int> >& selected) {
    selected.clear();
    vector<bool> added(V,false);
    //각각 최소 가중치의 간선의 가중치, 그 간선의 다른 한쪽 끝을 저장
    vector<int> minWeight(V,INF), parent(V,-1);
    int ret = 0;//가중치의 합
    //0번 정점을 시작점으로 MST를 찾기 시작하자
    minWeight[0] = parent[0] = 0;
    
    for(int iter = 0; iter < V; ++iter){
        int u = -1;
        for(int v = 0; v < V; ++v)//가장 작은 간선 하나 찾는다
            if(!added[v] && (u == -1 || minWeight[u] > minWeight[v]))
                u = v;
            
        if(parent[u] != u)//parent[u]와 u를 selected에 넣는다
            selected.push_back(make_pair(parent[u],u));
        ret += minWeight[u];
        added[u] = true;
            
        for(int i = 0; i < adj[u].size(); ++i){//minWeight를 갱신
            int v = adj[u][i].first, weight = adj[u][i].second;
            if(!added[v] && minWeight[v] > weight){
                parent[v] = u;
                minWeight[v] = weight;
            }
        }
    }
    return ret;
}

우선순위 큐를 이용한 구현

위의 코드는 다익스트라 알고리즘의 큐 없는 구현과 상당히 유사합니다. 또한 프림 알고리즘은 작동방식이, BFS와 묘하게 비슷하기 때문에, BFS의 변형이었던 다익스트라 알고리즘을 구현하듯이 우선순위 큐를 이용해서 구현할 수도 있습니다.

사실 바뀌는 부분은, 크게 없기에 바로 구현 들어가겠습니다.

const int MAX_V = 100;
const int INF = 987654321;
int V;
vector<pair<int,int> > adj[MAX_V];

int prim(vector<pair<int,int> >& selected) {
    selected.clear();
    vector<bool> added(V,false);
    //각각 최소 가중치의 간선의 가중치, 그 간선의 다른 한쪽 끝을 저장
    vector<int> minWeight(V,INF), parent(V,-1);
    priority_queue<pair<int,int> > pq;//가중치, 간선번호 순으로 넣자
    int ret = 0;//가중치의 합
    //0번 정점을 시작점으로 MST를 찾기 시작하자
    minWeight[0] = parent[0] = 0;
    pq.push(0,0);
    
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        if(added[u]) continue;//이미 MST에 넣은 건 한번더 볼 필요 없다
        if(parent[u] != u)
            selected.push_back(parent[u],u);
        added[u] = true;
        
        for(int i = 0; i < adj[u].size(); ++i){
            int v = adj[u][i].first,weight = adj[u][i].second;
            if(!added[v] && minWeight[v] > weight){
                minWeight[v] = weight;
                pq.push_back(-weight,v);
                parent[v] = u;
            }
        }
    }
    return ret;
}

어때요 참 간단하죠? 간선을 쭉 훑는데 $O(|E|)$ 가 들고, 우선순위 큐에서 하나 꺼내는데에 $O(lg|V|)$ 가 드니, 총 시간복잡도는 $(O(|E|lg|V|)$ 라고 할 수 있겠습니다.

참고한 글

https://ryute.tistory.com/12 : 크루스칼 알고리즘 증명부 작성하는데 참고
https://www.geeksforgeeks.org/prims-algorithm-using-priority_queue-stl/ : 우선순위 큐를 이용한 프림 알고리즘 작성에 참고

kasterra

블로그 이사했습니다. https://kasterra.github.io

이전 포스트