[c++] 프림 알고리즘

08 Dec 2023

프림 알고리즘(Prim’s algorithm)은 최소 신장 트리(Minimum Spanning Tree)를 찾기 위한 그리디 알고리즘 중 하나입니다. 최소 신장 트리란, 그래프 내의 모든 정점을 연결하면서 가중치가 가장 작은 트리를 말합니다.

알고리즘 개요

프림 알고리즘은 다음과 같은 단계로 동작합니다.

임의의 시작 정점을 선택하여 최소 신장 트리 집합에 포함시킵니다.
선택한 정점에 인접한 간선 중에서 가장 작은 가중치를 갖는 간선을 찾아 연결합니다.
연결된 정점을 최소 신장 트리 집합에 포함시킵니다.
모든 정점이 최소 신장 트리 집합에 포함될 때까지 2, 3 단계를 반복합니다.

예시 코드

다음은 C++로 구현된 프림 알고리즘의 예시 코드입니다.

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

#define V 5

using namespace std;

int minKey(int key[], bool mstSet[]) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; ++v)
        if (mstSet[v] == false && key[v] < min)
            min = key[v], min_index = v;

    return min_index;
}

void primMST(int graph[V][V]) {
    int parent[V];
    int key[V];
    bool mstSet[V];

    for (int i = 0; i < V; ++i)
        key[i] = INT_MAX, mstSet[i] = false;

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V-1; ++count) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < V; ++v)
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }

    cout << "Edge \tWeight\n";
    for (int i = 1; i < V; ++i)
        cout << parent[i] << " - " << i << " \t" << graph[i][parent[i]] << " \n";
}

시간 복잡도

프림 알고리즘의 시간 복잡도는 O(V^2) 또는 O(ElogV)로, 정점의 개수 V와 간선의 개수 E에 비례합니다. 이는 우선순위 큐를 사용하여 개선할 수 있습니다.

프림 알고리즘은 간선의 수가 적은 희소 그래프에서 효율적으로 동작하며, 피보나치 힙(Fibonacci Heap)을 사용하는 경우 더욱 효율적으로 만들 수 있습니다.

프림 알고리즘은 네트워크 설계, 도로 네트워크 구축, 회로 기판 레이아웃 등 다양한 응용 분야에서 사용됩니다.

알고리즘 개요

예시 코드

시간 복잡도

참고 자료