최소신장트리 - 크루스칼

최소신장트리를 만드는 알고리즘으로 크루스칼 알고리즘이 있다.

 

개념자체는 단순하다. 그래프의 모든 간선을 가중치의 순서대로 이어 붙인다.

 

그렇다면 중복되는 간선은 어떻게 걸러내야 할지 고민하게 된다.

 

이 방법은 집합 개념을 도입하여 해결한다. 

 

만약 최소 가중치의 간선을 최소신장트리에 포함하려 할 경우를 생각해 본다.

 

처음에는 아무도 집합을 이루지 않기에 바로 최소신장트리에 포함된다.

 

하지만 계속 반복되면 같은 집합 내에서 간선이 선택될 경우가 발생한다.

 

이는 순환을 발생시키므로 위와 같은 상황을 제외하면 최소신장트리가 완성된다.

vector<int> set;

int findParent(vector<int> set, int child) {
    int parent = set[child];
    while (parent != child) {
        child = set[child];
        parent = set[child];
    }
    return parent;
}

void union(){
	set[findParent(set, current.from)] = findParent(set, current.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;
    }
};

int findParent(vector<int> set, int child) {
    int parent = set[child];
    while (parent != child) {
        child = set[child];
        parent = set[child];
    }
    return parent;
}

void use_kruskal() {
    priority_queue<edge, vector<edge>, compare> pq;

    vector<int> set;
    int temp = 0;
    set.resize(10);

    for (int i = 0; i < set.size(); i++)
        set[i] = i;

    for (edge i : graph) 
        pq.push(i);
    
    while (!pq.empty()) {
        edge current = pq.top();

        pq.pop();

        if (findParent(set, current.from) != findParent(set, current.to)) {
            Mingraph.push_back(current);
            temp = current.from;
            current.from = current.to;
            current.to = temp;
            Mingraph.push_back(current);
            set[findParent(set, current.from)] = findParent(set, current.to);
        }
    }
}

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_kruskal();

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