최소신장트리 - 프림

프림알고리즘을 구현하려고 꽤 많은 시간을 사용했다.

 

그래프 구조라는 것에 대해 고민이 많았졌는데 

 

에초에 구조라는게 그냥 데이터를 관리하기 위해 정해놓은 룰이기도하고

 

뭔가 자료구조에대해 굉장히 모호해지고 어려워졌다....

 

 

 

 

어쨋든 프림 알고리즘은 그래프의 한 정점을 시작점으로 하여

 

가장 적은 가중치의 간선을 통해 탐색해 나가서 결국엔 최소의 가중치로 모든 정점을 그래프구조로 만들게된다.

 

이름은 최소신장트리 이지만 최소신장그래프도 가능한것이다.

 

 

 

그러면 크게 최소신장그래프를 저장하기위한 그래프를 선언하고

 

현재 가장 적은 가중치의 간선을 판단하기 위해 우선순위 큐를 사용한다.

 

그리고 전체적인 흐름은 다음과 같다.

 

 

 

우선순위 큐가 빌때까지 반복 {

우선순위 큐에서 간선 하나를 빼고 

이미 방문한 정점이면 컨티뉴

간선의 to를 방문했다고 표시

해당 정점(to)의 간선들을 우선순위 큐에 넣는다 > 기준은 가중치를 기준으로 넣음 

}

 

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

struct edge {
    int to;
    int from;
    int weight;
};

using namespace std;

vector<edge> graph;

vector<edge> Mingraph;

void appendEdge(int from, int to, int weight) {
    if (from < 0 || from >= 9)
        return;

    if (to < 0 || to >= 9)
        return;
    edge a;
    a.from = from;
    a.to = to;
    a.weight = weight;
    graph.push_back(a);

    a.from = to;
    a.to = from;

    graph.push_back(a);
}

struct compare {
    bool operator()(edge &a, edge &b){
        if (a.weight != b.weight)
            return a.weight > b.weight;
        return a.to > b.to;
    }
};

void use_prim(int start) {
    priority_queue<edge, vector<edge>, compare> pq;

    vector<bool> visited;

    visited.resize(graph.size(), false);

    for (edge into : graph) {
        if (into.from == start)
            pq.push(into);
    }
        

    visited[start] = true;

    edge startEdge;

    startEdge.from = 0;
    startEdge.to = start;
    startEdge.weight = 0;

    Mingraph.push_back(startEdge);

    while (!pq.empty()) {
        edge info = pq.top();

        pq.pop();

        if (visited[info.to])
            continue;

        visited[info.to] = true;

        Mingraph.push_back(info);

        for (edge into : graph)
            if (into.from == info.to)
                pq.push(into);
    }
}

int main()
{
    appendEdge(0, 1, 2);
    appendEdge(0,3,6);
    appendEdge(1,3,8);
    appendEdge(1,2,3);
    appendEdge(1,4,5);
    appendEdge(3,4,9);
    //appendEdge();

    for (edge info : graph) {
        cout << info.from << "--->" << info.to << "(" << info.weight << ")\n";
    }
    
    cout << "\n\n------------\n\n";

    use_prim(0);

    for (edge info : Mingraph) {
        cout << info.from << "--->" << info.to << "(" << info.weight << ")\n";
    }
    /*
    for (int i = 0; i < Mingraph.size(); i++) {
        cout << i << " : ";
        for (edge info : graph) {
            cout << info.to << "(" << info.weight << ")\t";
        }
        cout << "\n";
    }
    */
}