알고리즘 :: 크루스칼 알고리즘 Kruskal Algorithm (C/C++ 구현)

크루스칼 알고리즘 Kruskal Algorithm

크루스칼 알고리즘은 노드와 간선으로 이루어져있는 그래프에서

가장 적은 비용으로 노드들을 연결하는 알고리즘인다.

 

연결을 해보면 알겠지만, 

간선 = 노드 - 1 이라는 것을 알 수 있다.

 

순서대로 비용이 낮은 간선부터 연결을 한다.

이때, 사이클이 생기지 않도록 한다.

(사이클이 생길 경우, 그 간선은 무시하고 넘어간다.)

 

가장 적은 비용으로 모든 노드를 연결하는 알고리즘

 

크루스칼 알고리즘을 구현하기 위해,

Union Find(Disjoint set) 알고리즘을 활용한다.

Union Find 알고리즘이란?

2018/04/30 - [Algorithm] - 알고리즘 :: Union Find(Disjoint-Set) 알고리즘, 합 집합 찾기 알고리즘 (C/C++ 구현)

알고리즘 :: Union Find(Disjoint-Set) 알고리즘, 합 집합 찾기 알고리즘 (C/C++ /JAVA 구현)

 

힌트

간선 비용 정보들을 오름차순으로 나열한다. 

주의 할점은 사이클이 생기지 않도록 한다.

 

코드 구현

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

using namespace std;

// 부모노드를 가져옴
int getParent(int parent[], int node){
    if(parent[node] == node) {
        return node;
    }
    return getParent(parent, parent[node]);
}

// 두 노드의 부모노드를 합침
int unionParent(int parent[], int x, int y){
    x = getParent(parent, x);
    y = getParent(parent, y);
    if(x < y){
        parent[y] = x;
        return x;
    }else {
        parent[x] = y;
        return y;
    }
}

// 같은 부모노드를 갖는지 확인
int findParent(int parent[], int x, int y){
    x = getParent(parent, x);
    y = getParent(parent, y);
    if(x == y){
        // 같은 부모 노드
        return 1;
    }else{
        // 다른 부모 노드
        return 0;
    }
}

// 간선들의 정보
class Edge{
    public:
    int node[2];
    int distance;
    Edge(int x, int y, int distance){
        this->node[0] = x;
        this->node[1] = y;
        this->distance = distance;
    }
    bool operator <(Edge &edge){
        return this->distance < edge.distance;
    }
};

int main(int argc, char* argv[]) {
    int n = 7; // 노드의 개수
    int m = 11; // 간선의 개수
    vector<Edge> v;
    
    v.push_back(Edge(1, 7, 12)); // 1
    v.push_back(Edge(4, 7, 13)); // 2
    v.push_back(Edge(1, 4, 18)); // 3
    v.push_back(Edge(1, 2, 67)); // 4
    v.push_back(Edge(1, 5, 17)); // 5
    v.push_back(Edge(2, 4, 24)); // 6
    v.push_back(Edge(2, 5, 62)); // 7
    v.push_back(Edge(3, 5, 20)); // 8
    v.push_back(Edge(3, 6, 37)); // 9
    v.push_back(Edge(5, 6, 45)); // 10
    v.push_back(Edge(5, 7, 73)); // 11
    
    // 거리를 오름차순으로 정렬
    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);
        }// end if
    }// end for
    
    // 결과 확인
    cout << sum;
    
    return 0;
}
​

 

123이라는 결과를 얻을 수 있다.

 

관련 글

2018/04/30 - [Algorithm] - 알고리즘 :: Union Find(Disjoint-Set) 알고리즘, 합 집합 찾기 알고리즘 (C/C++ 구현)

알고리즘 :: Union Find(Disjoint-Set) 알고리즘, 합 집합 찾기 알고리즘 (C/C++ /JAVA 구현)