[c++] 프림 알고리즘(Prim's Algorithm) 최소 신장 트리 알고리즘

08 Dec 2023

프림 알고리즘은 그래프의 최소 신장 트리(Minimum Spanning Tree)를 찾기 위한 알고리즘 중 하나입니다. 최소 신장 트리는 그래프 내의 모든 정점을 포함하면서 어떤 코스트 함수가 정의된 경우에 그 값이 최소가 되는 트리입니다.

알고리즘 설명

프림 알고리즘은 아래와 같은 절차를 따릅니다:

시작 정점을 선택하고, 이 정점을 현재의 최소 신장 트리에 포함시킵니다.
현재의 최소 신장 트리에 속한 정점과 연결된 간선 중에서 가장 작은 가중치를 가진 간선을 선택합니다.
이 간선에 연결된 정점을 최소 신장 트리에 포함시킵니다.
위의 과정을 그래프 내의 모든 정점이 최소 신장 트리에 포함될 때까지 반복합니다.

프림 알고리즘은 주로 우선순위 큐(Priority Queue)를 사용하여 구현됩니다. 이를 통해 간선의 가중치를 기준으로 가장 작은 값을 선택할 수 있습니다.

C++ 예시

아래는 C++로 프림 알고리즘을 구현한 간단한 예시 코드입니다.

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

#define INF 0x3f3f3f3f

typedef pair<int, int> pii;

int prim(vector<vector<pii>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    vector<int> dist(n, INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    int mst_cost = 0;
    pq.push({0, 0});
    dist[0] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;
        mst_cost += dist[u];

        for (auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (!visited[v] && weight < dist[v]) {
                dist[v] = weight;
                pq.push({dist[v], v});
            }
        }
    }

    return mst_cost;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pii>> graph(n);

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

    int min_cost = prim(graph);
    
    cout << "Minimum Cost of Minimum Spanning Tree: " << min_cost << endl;
    return 0;
}

참고 자료

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. (CLRS 책)
GeeksforGeeks: Prim’s Algorithm for Minimum Spanning Tree
YouTube: 프림 알고리즘 동작 원리