C YC

IT Dev who working in Republic Of Korea

3 minute read

프림 알고리즘(Prim’s Algorithm) 이란?

프림 알고리즘은 가중치가 있는 연결된 무방향 그래프에서 최소 신장 트리를 찾는 알고리즘입니다.
크루스칼 알고리즘과 마찬가지로 탐욕 알고리즘(Greedy Algorithm)의 한 종류입니다.
핵심 아이디어는 하나의 정점에서 시작하여 MST(Minimum Spanning Tree, 최소 신장 트리)를 점차 확장해 나가는 것입니다.

prims
(출처 : https://pages.cs.wisc.edu/~daeyeon/)

특징

  • 탐욕 알고리즘: 각 단계에서 현재 MST에 연결된 간선 중 가장 가중치가 작은 간선을 선택합니다.
  • 정점 중심: MST를 구성하는 과정을 정점을 기준으로 진행합니다.
  • 우선순위 큐(Priority Queue) 활용: 최소 가중치 간선을 효율적으로 찾기 위해 우선순위 큐를 사용합니다.



동작 방식

  1. 시작 정점을 선택합니다.
  2. MST 집합을 생성하고, 시작 정점을 MST 집합에 추가합니다.
  3. MST 집합에 있는 정점들과 연결된 간선들을 모두 우선순위 큐에 넣습니다 (가중치가 낮은 순으로 정렬).
  4. 우선순위 큐가 비어 있지 않은 동안 다음을 반복합니다. a. 우선순위 큐에서 가장 가중치가 작은 간선을 꺼냅니다. b. 꺼낸 간선의 다른 쪽 정점이 MST 집합에 포함되어 있지 않다면, i. 해당 정점을 MST 집합에 추가합니다. ii. 해당 정점과 연결된 간선들을 우선순위 큐에 넣습니다.
  5. 모든 정점이 MST 집합에 포함되면 알고리즘을 종료합니다.



장단점

장점

  • 구현이 비교적 간단하고 직관적입니다. 프림 알고리즘은 하나의 정점에서 시작하여 MST를 단계적으로 확장해나가는 방식으로 동작하기 때문에, 알고리즘의 흐름을 이해하고 구현하기가 상대적으로 쉽습니다.
  • 밀집 그래프(Dense Graph)에서 효율적인 성능을 보입니다. 정점의 개수에 비해 간선의 개수가 많은 밀집 그래프의 경우, 프림 알고리즘은 크루스칼 알고리즘보다 더 빠른 성능을 나타낼 수 있습니다. 이는 프림 알고리즘이 정점을 중심으로 탐색을 진행하기 때문입니다.
  • 하나의 연결된 트리 형태로 MST를 구성합니다. 알고리즘의 특성상 항상 하나의 연결된 트리를 유지하며 MST를 만들어나가기 때문에, 중간 과정에서도 연결된 부분 트리를 확인할 수 있습니다.

단점

  • 희소 그래프(Sparse Graph)에서 성능이 저하될 수 있습니다. 간선의 개수가 정점의 개수에 비해 적은 희소 그래프의 경우, 프림 알고리즘은 불필요한 탐색을 수행할 수 있습니다. 이러한 경우에는 간선을 정렬하여 처리하는 크루스칼 알고리즘이 더 효율적일 수 있습니다.
  • 시작 정점에 따라 탐색 순서가 달라질 수 있습니다. MST의 형태는 유일하지만, 프림 알고리즘은 시작 정점을 어떻게 선택하느냐에 따라 탐색 순서가 달라질 수 있습니다. 물론 최종 결과인 MST의 가중치 합은 동일합니다.



예제

[인접 리스트, 우선순위 큐 사용]

#include <iostream>
#include <vector>
#include <queue>
#include <functional> // greater 사용을 위해 포함

using namespace std;

struct Edge {
    int to, weight;
};

int main() {
    int numVertices = 5;
    vector<vector<Edge>> adj(numVertices);

    // 간선 추가 (예시)
    adj[0].push_back({1, 2});
    adj[0].push_back({3, 6});
    adj[1].push_back({0, 2});
    adj[1].push_back({2, 3});
    adj[1].push_back({3, 8});
    adj[1].push_back({4, 5});
    adj[2].push_back({1, 3});
    adj[2].push_back({4, 7});
    adj[3].push_back({0, 6});
    adj[3].push_back({1, 8});
    adj[3].push_back({4, 9});
    adj[4].push_back({1, 5});
    adj[4].push_back({2, 7});
    adj[4].push_back({3, 9});


    vector<bool> inMST(numVertices, false); // MST에 포함된 정점 여부
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 우선순위 큐 (가중치, 정점)

    int startVertex = 0; // 시작 정점
    inMST[startVertex] = true;

    for (const auto& edge : adj[startVertex]) {
        pq.push({edge.weight, edge.to});
    }

    int mstWeight = 0;
    vector<pair<int,int>> mstEdges;

    while (!pq.empty()) {
        int weight = pq.top().first;
        int vertex = pq.top().second;
        pq.pop();

        if (!inMST[vertex]) { // MST에 포함되지 않은 정점인 경우
            inMST[vertex] = true;
            mstWeight += weight;
            //간선 저장
            for(int i = 0; i< numVertices; ++i){
                for(auto& edge : adj[i]){
                    if(edge.to == vertex && inMST[i]){
                        mstEdges.push_back({i, vertex});
                        break;
                    }
                }
            }
            

            for (const auto& edge : adj[vertex]) {
                if (!inMST[edge.to]) {
                    pq.push({edge.weight, edge.to});
                }
            }
        }
    }

    cout << "Minimum Spanning Tree:" << endl;
    for (const auto& edge : mstEdges) {
        cout << "(" << edge.first << ", " << edge.second << ")" << endl;
    }
    cout << "Total MST weight: " << mstWeight << endl;

    return 0;
}



[인접 행렬과 배열 사용]

#include <iostream>
#include <vector>
#include <limits> // numeric_limits 사용

using namespace std;

int main() {
    int numVertices = 5;
    vector<vector<int>> adj(numVertices, vector<int>(numVertices, numeric_limits<int>::max()));

    // 간선 추가 (예시)
    adj[0][1] = 2; adj[1][0] = 2;
    adj[0][3] = 6; adj[3][0] = 6;
    adj[1][2] = 3; adj[2][1] = 3;
    adj[1][3] = 8; adj[3][1] = 8;
    adj[1][4] = 5; adj[4][1] = 5;
    adj[2][4] = 7; adj[4][2] = 7;
    adj[3][4] = 9; adj[4][3] = 9;

    vector<int> minWeight(numVertices, numeric_limits<int>::max());
    vector<bool> inMST(numVertices, false);

    int startVertex = 0;
    minWeight[startVertex] = 0;

    int mstWeight = 0;
    vector<pair<int,int>> mstEdges;

    for (int count = 0; count < numVertices - 1; count++) {
        int u = -1;
        for (int v = 0; v < numVertices; v++) {
            if (!inMST[v] && (u == -1 || minWeight[v] < minWeight[u])) {
                u = v;
            }
        }

        inMST[u] = true;
        mstWeight += minWeight[u];
        
        for(int i = 0; i< numVertices; ++i){
            if(adj[u][i] != numeric_limits<int>::max() && inMST[i]){
                mstEdges.push_back({i, u});
            }
        }

        for (int v = 0; v < numVertices; v++) {
            if (!inMST[v] && adj[u][v] < minWeight[v]) {
                minWeight[v] = adj[u][v];
            }
        }
    }

    cout << "Minimum Spanning Tree:" << endl;
    for (const auto& edge : mstEdges) {
        cout << "(" << edge.first << ", " << edge.second << ")" << endl;
    }
    cout << "Total MST weight: " << mstWeight << endl;

    return 0;
}


Top

You May Also Enjoy

1 minute read