1. 프림 알고리즘 (Prim's Algorithm)

프림 알고리즘은 최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 알고리즘 중 하나입니다. 최소 신장 트리란, 하나의 그래프에서 모든 정점을 포함하면서 그래프의 간선 가중치의 합이 최소가 되는 트리를 말합니다.

프림 알고리즘은 그리디 알고리즘의 일종으로, 시작 정점을 선택한 후에 해당 정점과 인접한 간선 중 가장 작은 가중치를 가진 간선을 선택하며, 이 과정을 반복하여 최소 신장 트리를 찾습니다.

2. 알고리즘 동작 과정

1. 임의의 시작 정점을 선택합니다.
2. 선택한 정점과 연결된 간선 중 가장 작은 가중치를 가진 간선을 선택합니다.
3. 선택한 간선으로 연결된 정점을 트리에 추가합니다.
4. 추가된 정점과 연결된 간선 중 이미 트리에 포함된 정점과 연결된 간선은 제외합니다.
5. 모든 정점이 트리에 포함될 때까지 2~4 과정을 반복합니다.

3. 시간 복잡도

프림 알고리즘의 시간 복잡도는 일반적으로 O(ElogV)입니다. 이는 우선순위 큐를 사용할 경우에 해당하며, 배열을 사용하는 경우 시간 복잡도는 O(V^2)입니다.

4. 구현

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

using namespace std;

const int MAX = 1000;
const int INF = 987654321;

vector<pair<int, int>> graph[MAX];
bool visited[MAX];

int prim(int start) {
    int mst = 0; // 최소 신장 트리의 가중치 합
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // (가중치, 끝 정점) 형태의 간선 리스트를 저장하는 우선순위 큐

    visited[start] = true;
    for (auto e : graph[start]) {
        pq.push(e);
    }

    while (!pq.empty()) {
        int cost = pq.top().first;
        int to = pq.top().second;
        pq.pop();

        if (visited[to]) {
            continue;
        }

        visited[to] = true;
        mst += cost;
        for (auto e : graph[to]) {
            if (!visited[e.second]) {
                pq.push(e);
            }
        }
    }

    return mst;
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({w, v});
        graph[v].push_back({w, u});
    }

    cout << prim(0) << endl;

    return 0;
}