[C++] Prim MST 알고리즘(Greedy, priority queue활용) - 원더랜드

prim과 kruskal 둘 다 MST라서 구하고자하는 것은 같다. 하지만,
kruskal : 간선 정렬, Union & Find 활용
prim : 인접리스트, priority queue활용

 

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

int ch[30];

struct Edge{
    int e;
    int val;
    Edge(int a, int b){
        e = a;
        val = b;
    }
    bool operator<(const Edge &ref)const{
        //priority_queue에서 동작
        //최소힙을 만들어줌.
        return val > ref.val;
    }
};

int main() {
    priority_queue<Edge> Q;
    vector<pair<int, int>> map[30]; //인접리스트
    int i,n,m,a,b,c,res=0;
    scanf("%d %d",&n,&m);
    
    for(i = 1; i <= m; i++){
        scanf("%d %d %d",&a,&b,&c);
        map[a].push_back(make_pair(b, c));
        map[b].push_back(make_pair(a, c));//양방향 가중치 그래프 인접리스트
    }//문제에서 주어준 그래프 그리기
    
    Q.push(Edge(1,0));//노드 1에서 시작한다.
    
    while (!Q.empty()) {
        Edge tmp = Q.top(); //top 데이터 가져오고
        Q.pop();//바로 pop
        int v= tmp.e;//top데이터 노드번호 참조
        int cost = tmp.val;//top데이터 비용 참조
        if(ch[v] == 0){ //방문하지 않았다면
            res += cost;//코스트 누적
            ch[v] = 1;//방문했다.
            for(i = 0; i < map[v].size(); i++){//인접리스트와 연결된 노드 모두 참조
                Q.push(Edge(map[v][i].first, map[v][i].second));//Q에 담는다.
            }
        }
    }
    
    printf("%d\n",res);
    
    return 0;
}

• kruskal은 구조체형 1.vector에 노드와 간선 정보를 저장해놓고, 2.정렬한 후, 3.Union & Find로 연결하였다.
• Prim은 1.인접리스트로 미리 연결을 해놓고, 2.출발 노드를 priority queue로 지정해놓고 노드와 연결된 3.인접리스트를 탐색하면서 priority queue에 push한다.
• kruskal 구조체에는 v1, v2 ,val정보를 저장하고 vector를 활용했으나
• Prim은 인접리스트를 이용하였으므로 구조체에는 출발노드 e와 val만 저장한다.
• pirority queue에는 cost가 작은 것부터 오름차순으로 정렬되므로 비용이 작은 노드부터 탐색해나간다.
• 또한 이미 방문한 노드는 체크를 하기 때문에 Cycle이 발생하지 않는다.

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard