프림 알고리즘 (최소 신장 트리)

🟩 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장하는 기법

즉, 탐색 정점에 대해 연결된 인접 정점들 중 비용이 가장 적은 간선으로 연결된 정점을 선택

 

🟩 동작

1. 시작 단계는 시작 노드만이 최소 신장 트리 집합에 속한다.

2. 트리 집합에 속한 정점들과 인접한 정점들 중 가장 낮은 가중치의 간선과 연결된 정점에 대해 간선과 정점을 최소 신장 트리 집합에 넣는다 (사이클을 막기 위해 연결된 정점이 이미 트리에 속한다면 그 다음 순서를 넣는다)

3. 2번 과정을 MST 집합의 원소 개수가 그래프의 정점의 개수가 될 때까지  반복한다.

 

시작 정점 A

A와 인접한 노드 B, C 중 C가 가장 가중치가 낮은 간선으로 연결되어 있으니, C를 집합에 넣고 비용에 AC 가중치를 더한다.

AC와 인접한 노드들 중 가장 낮은 가중치로 연결된 정점은 B다. 집합에 B를 넣고 CB의 가중치를 더한다.

반복한 최종결과

A, B, C, D, E와 인접한 노드들 중 가장 낮은 가중치로 연결된 정점 F를 집합에 넣고 DF 가중치를 더한다.

트리의 집합에 속한 원소의 개수가 N이 되었으므로, 탐색을 중단한다. 탐색 결과 최소 신장 비용 트리는 13

 

🟩 원리

집합 내 정점들을 순회하면서 우선순위 큐에 삽입한 뒤 pop하여 구현하면 된다.

 

🟩 시간복잡도

인접 행렬의 경우 👉 O(V^2)

인접 리스트와  힙을 사용한 경우 👉 O(E logV)

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

using namespace std;

// 그래프의 정점 수
#define V 5

// 최소 키 값 찾기
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];
  
    // 키 값과 mstSet 배열 초기화
    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";
}

int main() {
    /* 그래프 표현 (인접 행렬)
          2    3
      (0)--(1)--(2)
      |   / \   |
     6| 8/   \5 |7
      | /     \ |
      (3)-------(4)
            9         */
    int graph[V][V] = {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0}
    };
  
    // 최소 신장 트리 구하기
    primMST(graph);
  
    return 0;
}