크루스칼 알고리즘(Kruskal Algorithm)에 대해 알아보자!!

Union-Find에 이어서 Kruskal ...

익숙해지자!!

Kruskal 이해하는데 

https://blog.naver.com/ndb796/221230967614 

님의 블로그 도움 많이 되었습니다.

1. Kruskal Algorithm 이란?

  - 최소 비용 신장 트리(MST)를 만들기 위한 대표적인 알고리즘입니다.

  - 그래프에서 가중치가 할당된 간선의 모든 정점을 비교하여 최소 비용으로 연결하여 최적 답을 구합니다.

  * 신장 트리(Spanning Tree) : 그래프내의 모든 정점을 포함하는 트리, n개의 정점이 가지는 최소 간선의 수는 n-1개이다.

    최소 비용 신장 트리(Mininum Spanning Tree) : 간선간의 가중치를 고려하여 가장 작은 가중치의 최소 비용의 Spanning Tree를 선택하는 것.

2. Kruskal Algorithm 과정

  

  ① 간선의 가중치를 오름차순으로 정렬하여 그래프에 포함시킨다.

노드	AC	BD	CD	EF	BC	AB	DF	DE	CE
가중치	1	1	1	2	3	3	4	5	6

  ② Disjoint-set을 통해 각각의 집합이였던 A와 C를 결합 연산을 사용하여 A와 C를 병합합니다. 

     그러면 A와 C는 하나의 집합이 되고, findParent 는 A입니다.

노드	AC	BD	CD	EF	BC	AB	DF	DE	CE
가중치	1	1	1	2	3	3	4	5	6

  ③ 마찬가지로 각각의 B와 D를 결합 연산을 통해 결합합니다. 

       B와 D는 하나의 집합이되고 Disjoint-set의 findParent 는 B입니다.

노드	AC	BD	CD	EF	BC	AB	DF	DE	CE
가중치	1	1	1	2	3	3	4	5	6

  ④ C와 D의 병합 연산을 함으로써 AC와 BD는 하나의 집합으로 ABCD가 되고, findParent는 A가 됩니다.

노드	AC	BD	CD	EF	BC	AB	DF	DE	CE
가중치	1	1	1	2	3	3	4	5	6

⑤ 다음으로 각각의 E와 F를 위와 같은 방법으로 결합합니다. E와 F는 하나의 집합이되고 findParent는 E입니다.

노드	AC	BD	CD	EF	BC	AB	DF	DE	CE
가중치	1	1	1	2	3	3	4	5	6

  ⑥ 다음단계에서 B와 C의 병합이지만, B의 findParent는 A입니다.

      C도 findParent는 A이기 때문에 같은 집합임을 알 수 있고, 그렇기 때문에 무시합니다. 

노드	AC	BD	CD	EF	BC	AB	DF	DE	CE
가중치	1	1	1	2	3	3	4	5	6

  ⑦ 마찬가지로 A와 B의 결합에서 B의 findParent가 A이고, 같은 집합임을 알 수 있기 때문에 무시합니다.

노드	AC	BD	CD	EF	BC	AB	DF	DE	CE
가중치	1	1	1	2	3	3	4	5	6

  ⑧ D와 F는 서로 다른 findParent이므로 서로 다른 집합임을 알 수 있고, 분리된 집합을 병합합니다.

노드	AC	BD	CD	EF	BC	AB	DF	DE	CE
가중치	1	1	1	2	3	3	4	5	6

 

  ⑨ 위와 같은 방법으로 DE와 CE는 결국 같은 집합이므로 무시합니다.

노드	AC	BD	CD	EF	BC	AB	DF	DE	CE
가중치	1	1	1	2	3	3	4	5	6

  ※ 결과

    - 모든 요소들의 findParent의 값이 A가 되면서 최소 비용 트리 신장을 만들었습니다.  

      이렇게 모든 요소들을 연결하는 비용은 1+1+1+2+4 = 9 인 것을 알 수 있습니다.

3. Kruskal Algorithm 구현

 #include<iostream>
 #include<algorithm>
 #include<vector>
 
 using namespace std;
 
 int getParent(int parent[], int x){
     if(parent[x] == x){
         return x;
     } else {
         return parent[x] = getParent(parent, parent[x]);
     }
 }
 
 void unionParent(int parent[], int x, int y) {
    x = getParent(parent, x);
    y = getParent(parent, y);
    if(x < y) {
        parent[y] = x;    
    } else {
        parent[x] = 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 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=6; // 노드의 수 
     int m=9; // 간선의 수
     
    vector<Edge> v;
    v.push_back(Edge(1, 2, 3)); 
    v.push_back(Edge(1, 3, 1));
    v.push_back(Edge(2, 3, 3));
    v.push_back(Edge(2, 4, 1));
    v.push_back(Edge(3, 4, 1));
    v.push_back(Edge(3, 5, 6));
    v.push_back(Edge(4, 5, 5));
    v.push_back(Edge(4, 6, 4));
    v.push_back(Edge(5, 6, 2));
    
    // 간선의 비용을 기준으로 오름차순 
    sort(v.begin(), v.end()); 
    
    // 그래프 저장
    int parent[n];
    for(int i=1; i<=n; i++) {
        parent[i] = i;
    } 
    int sum=0;
    for(int i=0; i<v.size(); i++) {
        if(!findParent(parent, v[i].node[0], v[i].node[1])) {
            sum += v[i].distance;
            unionParent(parent, v[i].node[0], v[i].node[1]);
        }
    }
    printf("최소신장트리 비용 : %d\n", sum);
 }

  ※ 결과화면