Prim MST(Minimum spanning Tree)을 이용한, 최소 비용 간선 구하기(최소 힙 priority queue 이용) in C++

각 정점을 연결하는 간선의 최소 연결합을 출력하는 코드

정점의 수 v, 모든 간선의 수 e,
e개의 간선에 대해서는 출발 정점, 도착 정점, 간선의 비용이 주어진다.

#include <iostream>
#include <queue>

using namespace std;

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

int v, e, res = 0;
int ch[1001];
priority_queue<Data> pQ;
vector<Data> graph[1001];

int main() {
    freopen("input.txt", "rt", stdin);
    cin >> v >> e;
    for (int i = 1; i <= e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(Data(b, c));
        graph[b].push_back(Data(a, c));
    }
    pQ.push(Data(1, 0));
    while (!pQ.empty()) {
        Data temp = pQ.top();
        pQ.pop();
        int e = temp.e;
        int val = temp.val;
        if (ch[e] == 0) {
            ch[e] = 1;
            res += val;
            for (int i = 0; i < graph[e].size(); i++) {
                pQ.push(Data(graph[e][i].e, graph[e][i].val));
            }

        }
    }
    cout << res;
    return 0;
}

임의의 시작정점을 정한뒤, 해당 정점에서 갈 수 있는 간선을, 우선순위 큐를 이용하여 val이 최소값인 것만을 res결과 값에 더한다.

• bool operator< (const Data &d) const : 우선순위 큐를 최소힙으로 다루기 위함이다.(pQ.top()은 최소값을 가리킨다.)
• graph[a].push_back(Data(b,c)), graph[b].push_back(Data(a, c)) : 무방향 그래프
• pQ.push(Data(1, 0)) : 임의의 시작정점이다.
• ch[1001] : 해당 정점을 방문하였는지를 기록한다.
  ex)
  9 12
  1 2 12
  1 9 25
  2 3 10
  2 8 17
  2 9 8
  3 4 18
  3 7 55
  4 5 44
  5 6 60
  5 7 38
  7 8 35
  8 9 15