기술면접 알고리즘 [Graph] : 프림 (Prim - Minimum Spanning Tree)

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다.

각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다.

---

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

프림 알고리즘은 Greedy 한 방식으로 Vertex 들을 이어 최소 신장 트리를 만든다. 구체적으로는 :

해당 정점의 집합 대해, 연결된 {간선, 정점} 쌍을 정점 가중치 기준으로 우선순위 큐에 넣는다. 그리고 가중치가 기존의 가중치보다 작으면서, 도착 지점이 미방문인 노드를 집합에 넣고, 추가된 노드의 {간선, 정점} 쌍들을 다시 우선순위 큐에 넣는다. 해당 작업을 모든 Vertex 를 순회할 때까지 반복하면 된다.

시간 복잡도는 (모든 정점에 대해서) * (우선순위 큐에서 정점 추출) + (모든 간선에 대해서) * (값 변경 및 우선순위 큐에 삽입) 이 되므로, O( V * log(V) + E * log(E) ) 가 되어, 최종적으로 O( E * log(E) ) 가 된다. (E 는 최대 V^2 이므로)

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

#define V   5
#define INF 1000000

struct myP {
    int v;
    int dist;
};

struct compare {
    bool operator()(myP a, myP b) {
        return a.dist > b.dist;
    }
};

void primMST(int (*graph)[V]) {

    std::priority_queue<myP, std::vector<myP>, compare> q;

    int dist[V];
    std::fill(dist, dist+V, INF);

    int parent[V];
    std::fill(parent, parent+V, -1);

    // pick node 0 as starting point
    dist[0] = 0;
    q.push({0, 0});

    bool visited[V];
    myP cur;
    while (!q.empty()) {
        cur = q.top();
        q.pop();

        int c_v = cur.v;
        int c_d = cur.dist;

        // relaxation
        visited[c_v] = true;
        dist[c_v] = c_d;

        for (int i = 0; i < V; ++i) {
            if (graph[c_v][i] && !visited[i] && dist[i] > c_d + graph[c_v][i]) {
                dist[i] = c_d + graph[c_v][i];
                parent[i] = c_v;
                q.push({i, dist[i]});
            }
        }
    }

    std::cout << "Edge  Weight" << std::endl;
    for (int i = 1; i < V; ++i) {
        std::cout << parent[i] << " - " << i << "\t" << graph[parent[i]][i] << std::endl;
    }
}


// Driver code
int main()
{
    /* Let us create the following graph
        2 3
    (0)--(1)--(2)
    | / \ |
    6| 8/ \5 |7
    | / \ |
    (3)-------(4)
            9     */
    int graph[V][V] = { { 0, 2, 0, 6, 0 },
                        { 2, 0, 3, 1, 11 },
                        { 0, 3, 0, 0, 7 },
                        { 6, 1, 0, 0, 9 },
                        { 0, 11, 7, 9, 0 } };
 
    // Print the solution
    primMST(graph);
 
    return 0;
}