Graph Algorithm - Prim's Algorithm

thewoowon·2022년 3월 2일
0

Algorithm

목록 보기
4/10

안녕하세요. 우원입니다.

오늘은 프림의 알고리즘을 작성하고 분석하겠습니다.

이전에 포스팅한 DFS, BFS를 참고하시면 더욱 좋습니다.

Graph Algorithm - DFS 바로가기
Graph Algorithm - BFS 바로가기

프림 알고리즘입니다.

#include <string>
#include <vector>
#include <iostream>
#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:
    Graph(unsigned N) : V(N) {}

    auto vertices() const { return V; }

    auto& edges() const { return edge_list; }

    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;
    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_vertax = heap.top();
        heap.pop();

        if (visited.find(current_vertax.ID) == visited.end())
        {
            MST.push_back(current_vertax.ID);

            for (auto& e : G.edges(current_vertax.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_vertax.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;
    cout << endl;
}

R.C.Prim에 대해서는 위키에 자세히 나와있습니다.

프림 알고리즘은 1930년에 체코의 수학자에 의해 최초발견되었고,
이후 프림과 다익스트라에 의해 독립적으로 발견되었습니다.

우선 프림 알고리즘을 분석하기 전,
우리는 최소 신장 트리의 개념과 크루스칼 알고리즘을 알고 가는 것이 좋습니다.
이전에 포스팅한 내용을 참고하시길 바랍니다.
Graph Algorithm - MST 바로가기

프림 알고리즘은 BFS의 동작 방식과 유사합니다.
프림 알고리즘은 먼저 시작 정점을 이용하여 경계를 구성합니다.
경계는 이전에 방문했던 정점들에 의해 구성되며, 현재 경계에 인접한 정점을 반복적으로 탐색합니다.
이때 프림 알고리즘은 경계를 관통하는 에지 중에서 가장 가중치가 작은 에지를 선택하고,
이 에지에 연결된 정점을 방문합니다.

프림 알고리즘은 그래프의 각 정점에 경계로부터의 거리 정보를 기록해야 구현됩니다.

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;
}

BFS와 다르게 에지에 각각 가중치가 부여되었습니다.
여기서 가중치의 의미는 정점 간 이동을 위한 비용이라고 생각하시면 됩니다.

부분 신장 그래프 = 신장 그래프 = 부분 신장 트리 != 부분 그래프 != 그래프

그래프 안에 connected, undirected, acyclic 세 가지 조건을 만족하는 것을 Tree라고 하기 때문에
결국 트리는 그래프의 부분집합이라고 생각하시면 됩니다.

그래프의 가중치는 네트워크 환경에서 가장 흔히 쓰입니다.

가중치 그래프 = 네트워크

예를 들어 국가간 비행기 노선의 가격이라고 생각하시면 됩니다.
8개의 나라가 있고 최소 7개의 간선이 존재하는 그래프가 있습니다.
모험가가 여행을 출발해 8개국을 모두 방문한 후, 발생한 총 비용은 이용한 비행기 노선의 값을 전부 더한 값입니다.
그러나 우리는 예산이 한정되어 있기 때문에 8개국을 최소한의 비용으로 이용하고 싶습니다.
이때 유용한 해결법이 MST를 구하는 크루스칼 알고리즘, 프림 알고리즘입니다.

template <typename T>
struct Label {
    unsigned ID;
    T 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_vertax = heap.top();
        heap.pop();

        if (visited.find(current_vertax.ID) == visited.end())
        {
            MST.push_back(current_vertax.ID);

            for (auto& e : G.edges(current_vertax.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_vertax.ID);
        }
    }
    return MST;
}

눈에 띄는 점은 Label입니다.
inline 키워드로 연산자를 오버로딩합니다.(부가적인 오버헤드를 줄이기 위함)
왼쪽에 오는 레이블의 길이가 더 크면 true을 그렇지 않으면 false를 반환합니다.

prim_MST()로 넘어가봅니다.
내부 컨테이너는 우선순위 큐 컨테이너로 최대힙을 통해 구현됩니다.
내부 비교 연산자로 greater를 통해 heap의 루트에는 가장 작은 수가 올 것임을 알 수 있습니다.

길이를 담는 벡터 객체를 선언하고 초기화합니다.
set은 단순히 방문 노드를 표시하기 위한 것이고 MST는 방문 노드의 실제 순서를 입력합니다.

여기서 주의해야하는 것은 distance 컨테이너입니다.
distance의 각 원소값은 current_vertax.ID가 가리키는 노드와 연결된 노드들의 상대적인 작은 값이 들어가게됩니다. 이 말은 즉슨 무조건 최단거리로 기록되고 그 안에서 pop()을 하면서 노드를 탐색한다는 것이됩니다.

말이 어렵지만 가장 좋은 방법은 중단점을 설정하고 조사식으로 값을 확인해보는 것이 좋다고 생각합니다.

다음은 다익스트라 알고리즘을 진행하겠습니다.

profile
요람에서 코드까지

0개의 댓글