[알고리즘] MST(Minimum Spanning Tree, 최소신장트리) - Kruskal, Prim 구현 (C++)

목차

1. Greedy 알고리즘이란

2. MST란

3. Kruskal 알고리즘

- 이론, 구현

4. Prim 알고리즘

- 이론, 구현

---

1. Greedy 알고리즘이란

Greedy 알고리즘이란 욕심장이 기법으로 당장 이 순간에서 최적이 되는 해를 구하는 것에, 즉 현재에 집중하는 알고리즘입니다. 과거와 미래는 전혀 신경쓰지 않습니다. Greedy 알고리즘의 핵심 단계는 다음과 같습니다. 

 

1) Selection Procedure (선택)

현재를 기준으로 가장 최적이 되는 해를 선택하는 단계입니다. 최적 해를 선택하여 집합에 추가합니다. 이 과정을 위해 선행되는 핵심은 어떤 값을 먼저 볼 것인지에 대한 우선순위 결정입니다. 

2) Feasibility Check (유효성 검사)

앞에서 선택한 해를 포함한 집합이 문제를 해결 가능한 집합인지를 판단합니다. 그렇지 않을 경우 해당 선택을 버리고 다시 이전 단계로 돌아갑니다.

3) Solution Check (해결 여부 확인)

현재 상태의 집합이 문제의 완전한 해답을 제공하는지 확인합니다. 해결할 수 없다면 다시 돌아가 위 과정을 수행합니다.

---

2. MST 란

Greedy 알고리즘을 이용하면 MST(Minimum Spanning Tree)문제를 해결할 수 있습니다.

MST란 모든 정점을 연결하면서 간선 가중치의 합이 최소가 되는 Spanning Tree입니다.

용어 정리
- Connected graph : 어떤 두 정점을 잡더라도 그 사이의 경로가 존재하는 그래프
- Cyclic graph (<-> Acyclinc graph) : 중복되는 간선 없이 자기 자신으로 돌아오는 path를 가진 그래프
- Spanning Tree : 그래프의 모든 정점을 포함하며 사이클이 없는 Connected Subgraph, V-1개의 간선을 가짐
- MST : 모든 정점을 연결하면서 간선 가중치의 합이 최소가 되는 Spanning Tree

 

아래 그림을 통해 직접 살펴봅시다.

(a)는 connected, weighted, undirected 그래프인 G입니다.

(c)는 G의 Spanning Tree(신장트리)라고 할 수 있습니다. 모든 정점(v1~v5)을 포함하며 사이클이 없고, 어떤 두 정점을 잡아도 그 사이에 경로가 존재하는 Connected 그래프이기 때문입니다. 

(d)는 G의 Spanning Tree 중에서도 Minimum Spanning Tree라고 할 수 있습니다. Spanning Tree의 조건을 모두 만족하면서 간선의 가중치 합이 최소가 되기 때문입니다. 다시 (c)를 보면 간선의 가중치 합은 1+3+6+5 = 15입니다. 하지만 (d)의 간선의 가중치 합은 1+3+4+2 = 10 이고, 이는 G의 모든 Spanning Tree 중 최솟값입니다. 

 

즉 우리가 해결하고자 하는 MST 문제는 G와 같은 그래프가 주어졌을 때, (d)와 같은 MST를 찾는 것입니다. 

MST를 구할 수 있는 Greedy 알고리즘은 두 가지가 있습니다. Kruskal의 알고리즘과 Prim의 알고리즘인데 하나씩 살펴봅시다.

 

---

 

3. Kruskal's Algorithm

크루스칼의 알고리즘은 MST를 구할 수 있는 Greedy한 알고리즘입니다. 간선의 Weight를 오름차순 정렬 후 작은 것부터 하나씩 선택해보고, Cycle을 체크합니다.

 

Greedy의 3단계에서 Kruskal의 알고리즘은 아래와 같이 작동합니다.

1) Selection Procedure

간선의 weight가 작은 것부터 하나씩 선택합니다. 선택한다는 것은 합집합으로 만드는 것입니다. 여기서 Union-Find가 사용됩니다.

2) Feasibility Check

앞 선택을 포함한 집합에서 Cycle이 형성된다면 위 선택을 버리고 다시 1단계로 돌아갑니다. 

3) Solution Check

모든 정점을 포함하는 그래프인지 확인합니다.

 

위 단계를 모두 통과하면 이는 MST입니다.

이 단계를 예시 그림을 통해 하나씩 따라가봅시다. 아래의 그래프는 위에서 우리가 보았던 그래프 G입니다.

1. 간선들(Edge)을 가중치를 기준으로 오름차순 정렬

Greedy한 접근에서는 어떤 값을 먼저 볼지가 중요합니다. MST는 간선의 합이 최소가 되어야 하므로 작은 값의 간선부터 탐색하도록 합니다.

 

2. 초기화

모든 정점을 Disjoint set(서로소 집합)으로 만들어줍니다. 이는 Union-Find에서의 init 과정입니다.

 

3. 간선 (v1,v2) 선택

간선의 오름차순 정렬 순대로 간선을 하나씩 취해보며 본격적인 Greedy 탐색을 시작합니다.

첫 번째 간선인 간선(v1,v2)을 먼저 선택합니다.(Step1) Cycle이 형성되지 않으므로 이 선택을 채택합니다.(Step 2) 하지만 아직 모든 정점을 연결하지는 않았으므로 아직 Spanning Tree가 아닙니다.(Step3)

 

4. 간선 (v3,v5) 선택

다음으로 작은 간선인 간선(v3,v5)을 선택합니다.(Step1) Cycle이 형성되지 않으므로 이 선택을 채택합니다.(Step2) 하지만 아직 MST는 아닙니다.(Step3)

 

5. 간선 (v1,v3) 선택

다음으로 작은 간선인 간선(v1,v3)을 선택합니다.(Step1) Cycle이 형성되지 않으므로 이 선택을 채택합니다.(Step2) 하지만 아직 MST는 아닙니다.(Step3)

 

6. 간선 (v2,v3) 선택

다음으로 작은 간선인 간선(v2,v3)을 선택합니다.(Step1) Cycle이 형성되므로 이 선택을 기각합니다.(Step2)

 

7. 간선 (v3,v4) 선택

다음으로 작은 간선인 간선(v3,v4)을 선택합니다.(Step1) Cycle이 형성되지 않으므로 이 선택을 채택합니다.(Step2) 모든 정점이 연결되었으므로 MST입니다.(Step3)

 

이렇게 MST를 구할 수 있습니다. 그런데 이제 Cycle 형성 여부를 체크하는 과정이 궁금해지는데요, 여기서 Union-Find가 사용됩니다. Step1에서 v1과 v2를 연결하는 간선을 선택했다면 Step2에서는 v1의 루트와 v2의 루트를 찾고, 두 루트가 같은지 비교합니다. 루트노드가 같다면 v1과 v2를 연결하는 간선을 추가하는 순간 사이클이 형성될 것입니다. 루트노드가 같지 않다면 두 정점을 연결하는 간선을 추가해도 문제가 없습니다.

---

 

그럼 이론적으로 로직을 모두 알았으니 이제 구현을 해봅시다!! C++로 작성하기 전에 수도 코드를 먼저 살펴봅시다. 

 

 

E의 간선들을 가중치를 기준으로 오름차순 정렬

F를 공집합으로 초기화, n개의 singleton set을 초기화

F에 있는 간선의 수가 n-1보다 작을 때 아래의 내용을 반복 ( = 모든 정점을 포함할 때까지 반복, 모든 정점을 포함하기 위한 간선의 최소 개수는 n-1개이므로)

{ 가장 작은 간선부터 하나씩 선택, e에 할당

간선 e를 연결하는 정점 두 개를 i,j 에 할당

정점 i의 루트 노드를 p, 정점 j의 루트노드를 q에 할당

p와 q가 다르면 간선을 연결해도 사이클이 형성되지 않으므로 union하고, F에 선택된 해당 간선 추가 }

---

 

실제 구현은 백준 문제를 풀면서 해봅시다. (BOJ #1197 최소 스패닝 트리, https://www.acmicpc.net/problem/1197)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, pair<int,int>>> V;
vector<int> parent;

int Find(int a){
    if(parent[a]!=a){
        parent[a] = Find(parent[a]);
    }
    return parent[a];
}

bool Union(int a, int b){
    int a_root = Find(a);
    int b_root = Find(b);
    if(a_root != b_root){
        parent[b_root] = a_root;
        return true;
    }else{
        return false;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int v,e; cin>>v>>e;
    int a,b,c;
    for(int i=0;i<e;i++){
        cin>>a>>b>>c;
        V.push_back(make_pair(c,make_pair(a,b)));
    }
    sort(V.begin(),V.end()); // 정렬
    parent.resize(v+1);
    
    for(int i=1;i<v+1;i++){
        parent[i] = i; // singleton set 초기화
    }
    int edgeNum = 0; // 선택된 간선의 개수
    int weightSum = 0; // MST 가중치 합
    for(int i=0;i<e;i++){
        if(edgeNum==v-1) break;
        int cost = V[i].first;         // 간선의 가중치
        int from = V[i].second.first; // 간선의 시작 정점
        int to = V[i].second.second;  // 간선의 끝 정점
        if(Union(from,to)){
            edgeNum++;
            weightSum += cost;
        }
    }
    cout<<weightSum<<"\n";
}

---

4. Prim 알고리즘

Prim 알고리즘은 MST를 구할 수 있는 또 다른 Greedy 알고리즘 중 하나입니다. 선택된 간선들 중 가장 가중치가 작은 가지에 대해 가장 가까운 정점(작은 가중치의 간선으로 연결된 정점)으로 뻗어나가는 방식입니다. 또 핵심적인 것은 어떤 정점과 연결되어 있는지, 그리고 가중치가 어떻게 되는지에 대한 정보를 담은 배열 2개를 함께 사용합니다.

 

Prim 알고리즘에서는 Greedy의 3단계가 아래와 같이 적용됩니다.

 

1) Selection Procedure

Prim 알고리즘에서 간선을 선택하는 기준은 현재 MST에 포함된 정점과 연결된 간선 중에서 가중치가 가장 작은 간선입니다. 이 단계에서는 우선순위 큐를 사용하여 최소 가중치 간선을 효율적으로 선택합니다.

 

2) Feasibility Check

Prim 알고리즘은 알고리즘의 동작 방식 자체가 사이클을 방지하도록 되어 있습니다. MST에 포함된 정점과 아직 MST에 포함되지 않은 정점을 연결하는 간선만을 고려하는데, 즉 이미 방문한 정점과 연결된 간선은 고려하지 않으므로 새로운 간선을 추가해도 사이클이 형성되지 않습니다. 따라서 명시적인 Feasibility Check가 필요 없습니다.

 

3) Solution Check

모든 정점을 포함하는 그래프인지 확인합니다.

 

 

아래 그림을 통해 단계 별로 Prim의 알고리즘을 이해해봅시다.

 

1. 정점 v1 선택

첫 번째로 정점 v1이 선택됩니다.

nearest 배열에 담긴 값은 정점의 번호입니다. 지금은 선택된 정점이 v1밖에 없으므로 nearest에는 모두 1이 담겨있습니다.

해당 정점과의 거리가 몇 인지는 distance 배열에 기록됩니다.

• v2의 경우 v1과 연결된 간선의 가중치가 1이기 때문에 distance[2](v2와 v1 사이 경로를 이루는 간선들의 가중치 최소합)가 1입니다.
• v3의 경우 v1과 연결된 간선의 가중치가 3이기 때문에 distance[3] = 3 입니다.
• v4의 경우 v1과 직접 연결되지는 않기 때문에 아직 v1에서 v4까지 연결되는 경로를 모릅니다. 따라서 distance[4] = inf 로, 무한대 값을 넣어둡니다.
• v5의 경우에도 마찬가지로 v1과 직접 연결되지는 않기 때문에 아직 v1에서 v5까지 연결되는 경로를 모릅니다. distance[5] = inf 입니다.

 

2. 정점 v2 선택

선택된 정점 v1에서 가장 가까운 정점은, 즉 가장 작은 가중치의 간선으로 연결된 정점은 distance가 1인 v2입니다. 따라서 다음 정점으로는 v2가 선택됩니다. v2와 인접한 정점들은 distance를 업데이트하게 될 수도 있습니다.

• v3의 경우 v2와의 거리가 3이지만, 원래 v1과의 거리도 3이었기에 같은 값이므로 업데이트해줄 필요가 없습니다.
• v4의 경우 distance가 inf였습니다. 이는 v4에 도달할 수 있는 방법이 없음을 의미합니다. 하지만 이제 v2를 선택해주었으므로 v4에 도달할 수 있는 경로가 생겼습니다. 따라서 v4에 가장 가까운 정점은 v2임을 표시해주기 위해 nearest[4] = 2를 기록합니다. 또한 그 거리는 6이므로 distance[4] = 6 으로 업데이트해줍니다.
• v5는 아직 도달할 수 있는 경로가 없습니다.

 

3. 정점 v3 선택

선택된 정점들 중에서 가장 가까운(distance가 작은) 정점이 v3이기 때문에 다음으로는 v3을 선택합니다. 마찬가지로 인접한 정점이 있을 경우 distance를 비교하고 더 작을 시 업데이트 해줍니다.

• v4는 v3과 4 떨어져 있으므로 nearest[4] = 3, distance[4] = 4 로 업데이트 해줍니다.
• v5까지 도달할 수 있는 경로도 생겼습니다. v3에서 가중치 2인 간선으로 연결되어 있으므로 nearest[5]=3, distance[5] = 2로 업데이트해줍니다.

 

4. 정점 v5 선택

선택된 정점들 중 가장 가까운 정점은 거리가 2인 v5이기 때문에 정점 v5를 선택합니다. 

• v4는 v5와 거리가 5인데, v3까지의 거리 4가 더 가까우므로 업데이트를 해주지 않습니다.

 

5. 정점 v4 선택

선택된 정점들 중 가장 가까운 정점인 v4를 선택합니다. 모든 정점이 선택되었으므로 MST가 완성되었습니다.

우리가 다음 정점을 선택할 때 가장 가까운 거리에 있는 정점을 선택했는데, 그 두 정점을 연결하는 간선들이 MST를 이룹니다.

 

---

이제 수도 코드입니다. 

 

오른쪽은 초기화하는 부분이고, 왼쪽이 핵심 코드입니다.

 

1. repeat (n - 1) time

그래프의 정점 개수 n 중 시작 정점을 제외한 나머지 n−1개의 정점을 MST에 추가하기 위해 이 루프를 반복합니다.

 

2. min = inf

현재 MST와 연결되는 최소 가중치를 저장할 변수 min을 초기화 합니다. 초기값을 inf로 설정하여 첫 번째 비교에서 항상 작은 값이 선택되도록 합니다. 

 

3. for(i=2;i<-n;i++) 

MST에 포함되지 않은 모든 정점을 확인하여 현재 MST와 연결된 가장 가까운 정점을 찾습니다. (v1은 보통 시작 정점이므로 i=2부터 확인합니다.)

 

4. if( 0 <= distance[i] < min )

0 <= distance[i] 은 아직 MST에 포함되지 않은 정점을 의미합니다. (뒤에서 MST 포함 정점을 음수로 초기화)

distance[i] < min 은 현재까지 찾은 정점들 중 가장 가까운 정점임을 의미합니다.

이 두 조건을 만족하면 min을 업데이트하고, 가장 가까운 정점의 인덱스를 저장하는 vnear를 업데이트 합니다. 

 

5. e = ~, distance[vnear] = -1

간선 e를 MST에 추가합니다. 정점 vnear가 이미 MST에 포함된 정점임을 나타내기 위해 distance[vnear]의 값을 -1로 설정합니다.

 

6. for(i=2;i<=n;i++) 내부

새로 MST에 추가된 정점 vnear를 기준으로 다른 정점들의 distance 값을 업데이트합니다. 정점 vi가 vnear를 통해 더 짧은 경로로 접근할 수 있다면 nearest[i]를 vnear로 설정하고 distance[i]를 업데이트 합니다.

---

Prim 알고리즘도 백준 문제를 통해 구현해보았습니다. (BOJ #1197 최소 스패닝 트리, https://www.acmicpc.net/problem/1197)

구현 단계에서는 가장 낮은 가중치의 간선을 빠르게 추출하기 위해서 Priority queue(우선순위 큐) 자료구조를 활용했습니다.

#include <iostream>
#include <vector>
#include <climits>
#include <queue>
using namespace std;

typedef pair<int, int> Edge; // 간선 정보 {가중치, 정점 번호}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int v,e; cin>>v>>e;
    int totalWeight = 0; // MST 가중치 합
    vector<vector<Edge>> adj(v+1); //인접리스트
    vector<bool> visited(v+1,false); //방문 여부
    int a,b,c;
    for(int i = 1;i<=e;i++){
        cin>>a>>b>>c;
        adj[a].push_back(Edge(c,b));
        adj[b].push_back(Edge(c,a)); // undirected
    }

    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
    visited[1] = true; // 시작 정점
    for(auto &edge : adj[1]){
        pq.push(edge);
    }

    int vCount = 0; // 선택된 정점 수
    while(!pq.empty()){
        int weight = pq.top().first;
        int next = pq.top().second;
        pq.pop();

        if(visited[next]) continue;

        visited[next] = true;
        vCount++;
        totalWeight += weight;
        if(vCount==v) break;

        for(auto &edge : adj[next]){
            if(!visited[edge.second]){
                pq.push(edge);
            }
        }
    }
    cout<<totalWeight<<"\n";
    return 0;
}

 

✍🏻 문제를 풀 때 놓쳤던 부분

• undirected graph이므로 인접 리스트를 만들 때 양쪽 정점 다 push를 해주어야 한다.

✍🏻 구현이 어려웠던 부분

• 인접리스트로 weighted 그래프를 표현하는 것!

---

 

처음에는 우선 순위 큐 자료구조를 사용하는 것이 익숙치 않아 우선순위 큐 대신 정렬을 하였습니다. 벡터 내 한 원소 안에 담겨 있는 벡터 컨테이너(Edges)를 가중치를 기준으로 정렬하는 것입니다. 구현은 하였으나 서버에 풀이를 올렸을 때는 시간초과가 발생했습니다.

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm> // for sort
using namespace std;

typedef pair<int, int> Edge; // 간선 정보 {가중치, 정점 번호}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int v,e; cin>>v>>e;
    int totalWeight = 0; // MST 가중치 합
    vector<vector<Edge>> adj(v+1); //인접리스트
    vector<bool> visited(v+1,false); //방문 여부
    int a,b,c;
    for(int i = 1;i<=e;i++){
        cin>>a>>b>>c;
        adj[a].push_back(Edge(b,c));
        adj[b].push_back(Edge(a,c));
    }
    for (auto &edges : adj){ // 가중치 작은 것부터 정렬
        sort(edges.begin(), edges.end(), [](Edge &a, Edge &b){
            return a.second < b.second;
        });
    }
    visited[1] = true; // 시작 정점
    for(int i = 0; i < v-1; i++){ //v-1개의 간선을 찾을 때까지 반복
        int minWeight = INT_MAX;
        int vnear = -1;
        for(int j=1;j<=v;j++){ // 가장 가까운 정점 찾기
            if(!visited[j]) continue;
            for(auto &edge : adj[j]){
                int vnext = edge.first;
                int nextWeight = edge.second;
                if(!visited[vnext] && nextWeight < minWeight){
                    vnear = vnext;
                    minWeight = nextWeight;
                    break;
                }
            }
        }
        visited[vnear] = true;
        totalWeight += minWeight;
    }
        cout<<totalWeight<<"\n";
}

 

 

 

 

---

 

 

알고리즘 교과목을 수강하면서 느끼고 있는 점은 생각보다 알고리즘의 개수가 많지 않다는 것이다.
예전에는 큰 틀을 그리지 못해 Greedy, MST, Union-Find 등등이 모두 별개의 알고리즘이었고, 이렇게 많은 것들을 어떻게 다 공부하지 싶었는데, 알고리즘 수업을 들어보니 큰 틀 아래 많은 것들이 있었고, 그 큰 묶음의 개수는 많지 않았다. 처음으로 느꼈던 것은 Recursion이다. 나는 재귀가 이렇게까지 많은 알고리즘을 관통하는 핵심적인 알고리즘인 줄 몰랐다. 이번에는 MST에 대해 배웠는데 이 역시 Greedy 알고리즘의 일종이었다. 이런 큰 범위의 알고리즘들이 작은 단위의 알고리즘을 아우른다. 작은 알고리즘들을 관통하는 그 핵심에 대해서 잘 다져야겠다는 생각을 했다. 

근데 Prim 알고리즘 구현이 너무 어려웠다. .. 오래 걸렸다.
Kruskal의 경우에는 이 알고리즘의 핵심이 되는 Union-find 알고리즘을 직전에 공부한 상태라 구현이 어렵지 않았는데, Prim에서는 인접리스트와 우선순위 큐 자료구조를 구현하는데 시간이 오래 걸렸다.