최소 스패닝 트리 - MST (크루스칼 알고리즘), (프림 알고리즘)

반갑습니다.

 

오늘은 최소 스패닝 트리 MST(Minimum Spanning Tree)에 대해서 공부해보겠습니다.

MST ( Minimum Spanning Tree ) 란?

기존의 그래프에서 신장 트리를 구성할 때 그 간선의 가중치 합이 제일 작은 신장 트리

• 모든 정점이 연결되어있다.
• 간선의 갯수는 정점의 갯수에 -1을 한 것이다.
• 간선에 가중치가 존재한다.
• 트리이기 때문에 사이클이 존재하지 않는다.

 

 

가중치가 있는 그래프에서 MST를 2가지 방법으로 추출 할 수 있다.

 

코드는 아래의 문제를 예시로 하여 작성하였습니다.

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

 

첫 번째: 크루스칼 알고리즘 (Kruskal's Algorithm)

간선 중심의 그리디 알고리즘이다.

 

동작 원리

1. 가중치를 기준으로 간선을 오름차순으로 정렬한다.
2. 선택한 가중치가 사이클을 만들지 않는 다면 MST에 추가한다.
3. 사이클을 만든다면 MST에서 제외한다.
4. MST의 간선의 갯수가 정점 -1 갯수가 될 때까지 반복한다.

사이클의 여부는 parent Vector에 root 경로를 메모제이션으로 기억해 동일한 root라면 사이클이 존재하는 것이다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct node {
    int st, en, we;

    bool operator < (const node& other) const {
        return we < other.we;
    }
};

int find(vector<int> &parent, int x) {
    if (parent[x] == 0) {
        return x;
    }
    return parent[x] = find(parent, parent[x]);
}

int main() {

    int v, e;

    cin >> v >> e;

    vector<node> list;
    vector<int> parent(v+1,0);

    int st, en, we;
    for (int i = 0; i < e; i++) {
        cin >> st >> en >> we;

        list.push_back({st, en, we});
    }

    sort(list.begin(), list.end());

    int sum = 0;
    int ct = 0;



    for (auto i : list) {
        if (ct == v-1) {
            break;
        }

        int findBy1 = i.st;
        int findBy2 = i.en;

        findBy1 = find(parent, findBy1);
        findBy2 = find(parent, findBy2);

        if (findBy1 != findBy2) {
            parent[findBy1] = findBy2;
            sum+=i.we;
            ct++;
        }

    }

    cout << sum;
}

 

 

두 번째: 프림 알고리즘 (Prim's Algorithm)

정점 중심의 그리디 알고리즘이다.

 

동작 원리

1. 아무 정점이나 정한다.
2. MST에 포함된 정점들에서 MST에 포함되지 않는 정점으로 가는 간선들 중 가중치가 가장 작은 간선을 선택 하여 해당 정점을 MST에 추가한다.
3. MST 정점의 갯수와 그래프의 정점의 갯수가 동일하면 종료한다

 

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;


int main()
{
    int v, e;

    cin >> v >> e;

    vector<bool> visit(v+1, false);
    vector<int> key(v+1, INT_MAX);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    vector<vector<pair<int, int>>> adj(v+1);

    for (int i = 0; i < e; i++)
    {
        int st, en, val;

        cin >> st >> en >> val;

        adj[st].push_back({en, val});
        adj[en].push_back({st, val});
    }


    key[1] = 0;
    pq.push({0, 1});

    int sum = 0;
    while (!pq.empty())
    {
        auto [dist, val] = pq.top();
        pq.pop();

        if (visit[val]) continue;
        visit[val] = true;

        for (auto i : adj[val])
        {
            if (!visit[i.first] && i.second < key[i.first])
            {
                key[i.first] = i.second;
                pq.push({i.second, i.first});
            }
        }
    }

    for (int i = 1; i <= v; i++)
    {
        sum += key[i];
    }
    cout << sum;
}