[Algorithm] Minimum Spanning Tree - Prim

1. Prim 알고리즘은 최소 신장트리를 우선순위 큐를 통해 찾는다.

2. BFS 알고리즘에서 그래프 가중치가 존재하는 경우라고 보면 될 것 같고, 우선순위 큐를 사용한다는 점 이외에 알고리즘은 동일하다.

3. 최소 힙을 통해 가중치가 가장 작은 간선부터 탐색해 나가고, 각 노드를 방문했는지 체크하는 과정을 통해 싸이클을 막을 수 있다.

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

using namespace std;

/*
최소 신장 트리 (MST)
1. Kruscal 알고리즘: Union-find 알고리즘을 활용
2. Prim 알고리즘: priority-queue
*/
int ch[30];
struct Edge{
    int e;
    int val;

    Edge(int a, int b){
        e=a;
        val=b;
    }
    bool operator<(const Edge &b) const {
        return val>b.val;
    }
};

int main()
{
    // freopen("78.txt", "r", stdin);
    priority_queue<Edge> pq;
    int i, n, m, a, b, c, cnt=0, res=0;
    cin >> n >> m;

    vector<pair<int, int> > map[30];
    for (i=1; i<=m; i++){
        cin>>a>>b>>c;
        // 무방향 가중치 그래프
        map[a].push_back(make_pair(b, c));
        map[b].push_back(make_pair(a, c));
    }
    // 시작 지점 1번 정점, 가중치 0
    pq.push(Edge(1, 0));
    while (!pq.empty())
    {
        Edge tmp = pq.top();
        pq.pop();
        int v = tmp.e;
        int cost = tmp.val;
        if (ch[v]==0) {
            res+=cost; 
            ch[v] = 1;
            for (int i=0; i<map[v].size(); i++){
                pq.push(Edge(map[v][i].first, map[v][i].second));
            }
        }
    }
    
    cout << res << endl;

    return 0;
}