[Algorithm] Prim 알고리즘

Prim 알고리즘이란?

Prim 알고리즘이란, 그래프에서 MST 를 찾는 알고리즘입니다. MST 가 무엇인지 모르신다면 아래 링크를 참고해주세요.

Spanning Tree 와 MST

[Algorithm] Spanning Tree 와 MST, 스패닝 트리와 최소 스패닝 트리

이 알고리즘은 MST 를 찾기 위해서 시작 정점에서부터 단계적으로 확장해나갑니다. 특이한 점은 MST 를 찾기위해서는 간선을 선택해야 하지만 Prim 은 정점 선택을 기반으로 합니다. 정점을 선택해서 어떻게 간선을 찾을지 알고리즘을 과정을 통해 알아보도록 합시다.

 

알고리즘 과정

• 시작 정점을 spanning tree 집합에 넣어줍니다.
• spanning tree 집합에 인접한 정점들 중에서 최소 간선으로 연결될 수 있는 정점을 spanning tree 집합에 넣어주고 이 때의 간선은 spanning tree의 간선이 됩니다.
• 이 과정을 간선이 n-1개가 되도록 반복합니다.

아래와 같은 상황에서 Kruskal 알고리즘이 MST 를 어떻게 찾는지 따라가보도록 하겠습니다.

 

우선 시작 정점을 1 이라 하고 spanning tree 집합에 넣습니다. 해당 집합에서 각 정점까지 이동할 수 있는 최소 가중치를 기록해서 가장 작은 정점을 집합에 포함하며 그 간선을 추가해주는 과정을 반복해줍니다. 그 결과 아래 표와 같은 결과를 얻을 수 있습니다.

i	1	2	3	4	5	6	7	MST 간선	spanning tree 집합
1	0	67	-	28	17	-	12	-	1
2	0	67	-	13	17	-	0	{(1,7)}	1,7
3	0	24	-	0	17	-	0	{(1,7),(7,4)}	1,7,4
4	0	24	-	0	17	-	0	{(1,7),(7,4),(1,5)}	1,7,4,5
5	0	24	20	0	0	45	0	{(1,7),(7,4),(1,5),(5,3)}	1,7,4,5,3
6	0	24	0	0	0	37	0	{(1,7),(7,4),(1,5),(5,3),(4,2)}	1,7,4,5,3,2
7	0	0	0	0	0	37	0	{(1,7),(7,4),(1,5),(5,3),(4,2),(3,6)}	1,7,4,5,3,2,6
8	0	0	0	0	0	0	0

포함한 간선의 가중치를 모두 더하면,

12+13+17+20+24+28+37+45+62+67+73 = 123 이 됩니다.

 

구현

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

1922번: 네트워크 연결

백준에 MST 를 찾는 문제가 있어서 해당 문제를 풀어보았습니다.

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

struct Edge {
    int start;
    int end;
    int cost;
    Edge() : start(0), end(0), cost(0) {
    }
    Edge(int start, int end, int cost) : start(start), end(end), cost(cost) {
    }
    bool operator < (const Edge &edge) const {
        return cost > edge.cost;
    }
};

vector<pair<int,int>> a[1001];
bool c[1001];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i=0; i<m; i++) {
        int start, end, cost;
        cin >> start >> end >> cost;
        a[start].push_back(make_pair(end,cost));
        a[end].push_back(make_pair(start,cost));
    }
    c[1] = true;
    priority_queue<Edge> q;
    // 시작 노드를 1로 하고 q 에 1 과 연결된 노드들을 넣어줌
    for (int i=0; i<a[1].size(); i++) {
        q.push(Edge(1, a[1][i].first, a[1][i].second));
    }
    int ans = 0;
    for (int i=0; i<n-1; i++) {
        Edge e;
        // 우선순위 큐이기 때문에 top 의 값은 가장 작은 값
        while (!q.empty()) {
            e = q.top();
            q.pop();
            if (c[e.end] == false) {
                break;
            }
        }
        c[e.end] = true;
        ans += e.cost;
        int x = e.end;
        for (int i=0; i<a[x].size(); i++) {
            q.push(Edge(x, a[x][i].first, a[x][i].second));
        }
    }
    cout << ans << "\n";
    return 0;
}