프림의 최소 신장 트리 알고리즘(Prim's Minimum Spanning Tree Algorithm)

프림의 최소 신장 트리 알고리즘(Prim's Minimum Spanning Tree Algorithm)

• MST 문제
  • 정점 집합 V의 가중치를 갖는 에지 집합 E로 구성된 그래프 G = <V, E>가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하는 문제
• 크루스칼 알고리즘(Kruskal Algorithm)
  • 그래프의 모든 에지를 최소 힙 에 추가하고, 사이클을 만들지 않는 최소 가중치의 에지를 이용하여 MST를 구성함.
• 프림 알고리즘(Prim's Algorithm)
  • BFS의 동작 방식과 유사함.
  • 먼저 시작 정점을 이용하여 경계를 구성함.
    • 경계는 이전에 방문했던 정점들에 의해 구성됨.
    • 현재 경계에 인접한 정점을 반복적으로 탐색함.
  • 이때 프림 알고리즘은 경계를 관통하는 에지 중에서 가장 가중치가 작은 에지를 선택하고, 이 에지에 연결된 정점을 방문함.
• 프림 알고리즘의 구현
  • 그래프의 각 정점에 경계로부터의 거리(Distance) 정보를 기록해야 함.
• 시간 복잡도
  • 이진 최소 힙과 MSt 저장을 위해 인접 리스트를 사용하여 구현한 프림 알고리즘의 시간 복잡도는 O(ElogV)
  • 피보나치 최소 힙(Fibonacci Min-Heap) 이라고 부르는 힙 구조를 사용할 경우, 시간 복잡도는 O(E + VlogV)로 향상됨.
• 프림 알고리즘 vs. 크루스칼 알고리즘
  • 모두 그리디 알고리즘 의 일종
  • 차이점
    • 크루스칼 알고리즘
      • 그래프의 최소 가중치 에지를 차례대로 추가하여 MST를 구성함.
      • 가장 널리 알려진 시간 복잡도 : O(ElogV)
      • 주로 적은 수의 에지로 구성된 희소 그래프(Sparse Graph) 에서 사용됨.
    • 프림 알고리즘
      • 그래프의 아무 정점부터 시작하여 MST를 구성함.
      • 가장 널리 알려진 시간 복잡도 : O(E + VlogV)
      • 주로 많은 수의 에지로 구성된 밀집 그래프(Dense Graph) 에서 사용됨.

 

동작 순서

①

• 모든 정점의 거리 값을 무한대로 초기화함.
• 시작 정점에서 자기 자신까지의 거리는 0이므로, 시작 정점의 거리 값은 0으로 설정함.
• 그리고 모든 거리 값을 최소 힙 H에 추가함.

• 정점 안의 숫자 : 정점 ID
• 정점 옆에 있는 빨간색 글자
  • 경계에서 해당 정점까지의 거리
  • 정점의 거리 값은 무한대로 초기화되어 있음.
  • 시작 정점인 1번 정점은 거리 값을 0으로 설정하였음.
• 에지 옆 검은색 숫자 : 에지 가중치

②

• 최소 힙 H로부터 정점을 하나 꺼냄.
  • 이 정점을 U라고 하면, 정점 U는 경계에서 가장 가까이 있는 정점임.
  • 이 정점을 MSt에 추가하고, 이 정점을 포함하도록 경계를 새로 설정함.

③

• U와 인접한 모든 정점 V에 대해, 만약 V의 거리 값이 (U, V)의 에지 가중치보다 크면, V의 거리 값을 (U, V)의 에지 가중치로 설정함.

• 1번 정점과 연결된 2번과 5번 정점의 거리 값이 각각 2와 3으로 변경된 것을 볼 수 있음.
• 이러한 과정을 정점 U에 안착(Settle)했다 라고 함.

④

• 방문하지 않은 정점이 남아 있다면 ②단계로 이동함.

• 2번 정점을 방문한 후의 그래프 상태
• 빨간색 에지 : 현재까지 구성된 MST

⑤

• 모든 정점에 대해 안착한 후, 다음과 같이 최종 MST가 생성됨.

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <limits>
using namespace std;

template <typename T>
struct Edge {
    unsigned src;
    unsigned dst;
    T weight;
};

template <typename T>
class Graph {
public:
    // N개의 정점으로 구성되 그래프
    Graph(unsigned N) : V(N) {}

    // 그래프의 정점 개수 반환
    auto vertices() const { return V; }

    // 전체 에지 리스트 반환
    auto& edges() const { return edge_list; }

    // 정점 v에서 나가는 모든 에지를 반환
    auto edges(unsigned v) const {
        vector<Edge<T>> edges_from_v;
        for (auto& e : edge_list) {
            if (e.src == v) {
                edges_from_v.emplace_back(e);
            }
        }

        return edges_from_v;
    }

    void add_edge(Edge<T>&& e) {
        // 에지 양 끝 정점 ID가 유효한지 검사
        if (e.src >= 1 && e.src <= V && e.dst >= 1 && e.dst <= V) {
            edge_list.emplace_back(e);
        }
        else {
            cerr << "에러: 유효 범위를 벗어난 정점!" << endl;
        }
    }

    // 표준 출력 스트림 지원
    template <typename U>
    friend ostream& operator<< (ostream& os, const Graph<U>& G);

private:   
    unsigned V;     // 정점 개수
    vector<Edge<T>> edge_list;
};

template <typename U>
ostream& operator<< (ostream& os, const Graph<U>& G) {
    for (unsigned i = 1; i < G.vertices(); i++) {
        os << i << ":\t";

        auto edges = G.edges(i);
        for (auto& e : edges) {
            os << "{" << e.dst << ": " << e.weight << "}, ";
        }

        os << endl;
    }

    return os;
}

template <typename T>
auto create_reference_graph() {
    Graph<T> G(9);

    map<unsigned, vector<pair<unsigned, T>>> edge_map;
    edge_map[1] = { {2, 2}, {5, 3} };
    edge_map[2] = { {1, 2}, {5, 5}, {4, 1} };
    edge_map[3] = { {4, 2}, {7, 3} };
    edge_map[4] = { {2, 1}, {3, 2}, {5, 2}, {6, 4}, {8, 5} };
    edge_map[5] = { {1, 3}, {2, 5}, {4, 2}, {8, 3} };
    edge_map[6] = { {4, 4}, {7, 4}, {8, 1} };
    edge_map[7] = { {3, 3}, {6, 4} };
    edge_map[8] = { {4, 5}, {5, 3}, {6, 1} };

    for (auto& i : edge_map) {
        for (auto& j : i.second) {
            G.add_edge(Edge<T>{ i.first, j.first, j.second });
        }
    }

    return G;   
}

template <typename T>
struct Label {
    unsigned ID;
    T distance;

    // Label 객체 비교는 거리(distance) 값을 이용
    inline bool operator> (const Label<T>& l) const {
        return this->distance > l.distance;
    }
};

template <typename T>
auto prim_MST(const Graph<T>& G, unsigned src) {
    // 최소 힙
    priority_queue<Label<T>, vector<Label<T>>, greater<Label<T>>> heap;

    // 모든 정점에서 거리 값을 최대로 설정
    vector<T> distance(G.vertices(), numeric_limits<T>::max());

    set<unsigned> visited;        // 방문한 정점
    vector<unsigned> MST;         // 최소 신장 트리

    heap.emplace(Label<T>{src, 0});

    while (!heap.empty()) {
        auto current_vertex = heap.top();
        heap.pop();

        // 현재 정점을 이전에 방문하지 않았다면
        if (visited.find(current_vertex.ID) == visited.end()) {
            MST.push_back(current_vertex.ID);

            for (auto& e : G.edges(current_vertex.ID)) {
                auto neighbor = e.dst;
                auto new_distance = e.weight;

                // 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면
                // 힙에 추가하고, 거리 값을 업데이트함.
                if (new_distance < distance[neighbor]) {
                    heap.emplace(Label<T>{neighbor, new_distance});
                    distance[neighbor] = new_distance;
                }
            }
            visited.insert(current_vertex.ID);
        }
    }
    return MST;
}

int main() {
    using T = unsigned;

    // 그래프 객체 생성
    auto G = create_reference_graph<T>();
    cout << "[입력 그래프]" << endl;
    cout << G << endl;

    auto MST = prim_MST<T>(G, 1);

    cout << "[최소 신장 트리]" << endl;
    for (auto v : MST) {
        cout << v << endl;
    }

    return 0;
}

 

결과

[입력 그래프]
1:      {2: 2}, {5: 3},
2:      {1: 2}, {5: 5}, {4: 1},      
3:      {4: 2}, {7: 3},
4:      {2: 1}, {3: 2}, {5: 2}, {6: 4}, {8: 5}, 
5:      {1: 3}, {2: 5}, {4: 2}, {8: 3},
6:      {4: 4}, {7: 4}, {8: 1},
7:      {3: 3}, {6: 4},
8:      {4: 5}, {5: 3}, {6: 1},

[최소 신장 트리]
1
2
4
3
5
7
8
6