크루스칼 알고리즘(Kruskal's Algorithm)

Kruskal's Algorithm

최소 비용 신장 부분 그래프를 찾는 알고리즘

 

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

using namespace std;


int getParent(int parent[], int x){
    if(parent[x] == x) return x;
    return parent[x] = getParent(parent,parent[x]);
}

int unionParent(int parent[],int a, int b){
    a = getParent(parent,a);
    b = getParent(parent,b);
    if(a<b) parent[b] = a;
    else parent[a]=b;
}

int findParent(int parent[], int a, int b){
    a = getParent(parent,a);
    b = getParent(parent,b);
    if(a ==b) return 1;
    return 0;
}

class Edge{
public:
    int node[2];
    int distance;
    Edge(int a, int b, int distance){
        this ->node[0] = a;
        this ->node[1] = b;
        this -> distance = distance;
    }
    bool operator<(Edge &edge) {
        return this->distance <edge.distance;
    }
};

int main(void){
    int n = 7;
    int m = 11;
    vector<Edge> v;
    v.push_back(Edge(1,7,12));
    v.push_back(Edge(1,4,28));
    v.push_back(Edge(1,2,67));
    v.push_back(Edge(1,5,17));
    v.push_back(Edge(2,4,24));
    v.push_back(Edge(2,5,62));
    v.push_back(Edge(3,5,20));
    v.push_back(Edge(3,6,37));
    v.push_back(Edge(4,7,13));
    v.push_back(Edge(5,6,45));
    v.push_back(Edge(5,7,73));
    
    sort(v.begin(), v.end());
    
    int parent[n];
    for(int i = 0; i<n;i++){
        parent[i] =i;
    }
    
    int sum = 0;
    for(int i =0; i<v.size();i++){
        if(!findParent(parent, v[i].node[0]-1,v[i].node[1]-1)){
            sum += v[i].distance;
            unionParent(parent,v[i].node[0]-1, v[i].node[1]-1);
        }   
    }
    printf("%d\n", sum);
}

앞의 Union-Find를 사용하며 Edge class를 작성하는 방법

Edge 클래스를 json 으로 표현 하자면 이런 느낌일까

{

   "Edge":{

      "node1": a,
      "node2": b,
      "distance": distance

    }

}

Edge class안에 operation을 distance 기준으로 정렬하게 해 준뒤 sort()

이후에 n만큼의 배열을 만든 뒤 초기화

distance의 합을 저장할 sum 초기화

이후에 Union-Find를 통해 sum 계산