[알고리즘] 크루스칼 알고리즘 ( Kruskal Algorithm)

[개념]

 

크루스칼 알고리즘은 

모든 노드들을 최소 비용으롤 연결하는 알고리즘이다.

N개의 노드를 N-1개의 간선으로 연결 

 ex) 모든 도시를 도로로 연결할 때 가장 적은 비용으로 연결하는 방법

 

1. 노드 간의 연결 정보를 저장하고 비용을 기준으로 오름차순으로 정렬한다.

2. 비용이 적은 것부터 연결 

이 때 사이클이 발생하지 않도록 주의

==> Union-Find 를 사용해 확인, 노드를 연결할 때 부모가 같다면 이미 연결된 것이므로 제외

3. 현재 간선을 현재  MST 집합에 추가 

 

 

아래 그림과 같이 가중치를 기준으로 오름차순으로 정렬한다.

가중치가 작은 것부터 선택하여 노드를 서로 연결한다.

해당 예제에서는 2번 노드와 5번 노드를 연결한다.

 

(아래 그림에서 방향 그래프로 그렸는데 잘못 그렸습니다. 크루스칼 알고리즘에서는 방향이 없습니다. ) 

 

 

그 다음으로 가중치가 작은 6번 노드와 1번 노드를 연결한다.

 

 

 

 

이제 5->4번을 연결해준다.

 

 

 

다음으로 4->2를 연결해야 하는데

연결하게 되는 경우 사이클이 발생한다.

따라서 연결하지 않고 다음으로 넘어가서 4->3을 연결한다.

 

 

 

 

 

마지막으로 3->6까지 연결하면 5개의 간선 ( N-1)으로 N개의 노드를 모드 연결할 수 있다.

이와 같은 방법으로 MST를 구하는 것을 쿠르스칼 알고리즘이라고 한다.

 

 

 

[코드]

 

노드가 총 5개라고 하자.

node배열에는 node간의 연결 정보를 저장한다. 

vector에는 간선 길이와 node 배열에서의 index를 저장한다.

 

즉 node[0] = {1,2};는 1번 노드와 2번 노드를 연결한 것이다.

또한 v[0]={10,0}에는 0번 index에 대한 간선의 길이가 저장되어있다. 

따라서 1번 노드와 2번 노드 사이의 간선 길이는 10이라는 것을 알 수 있다.

 

노드간의 연결정보를 저장하고  Kruskal 함수에서 간선 길이를 기준으로 오름차순으로 정렬한다.

이 때 Find 함수를 통해 parent가 같은지 확인한다.

Parent가 같다는 것은 이미 연결이 된 것이고 , 여기서 또 Union을 하면 Cycle이 발생한다.

이와 같이 간선의 길이를 기준으로 짧은 것부터 연결을 하고

마지막에 Find 함수를 통해서 각 노드의 parent를 통해 모든 노드가 연결이 되었는지 확인할 수 있다.

(parent가 하나라도 다르면 모두 연결되지 않을 것)

 

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

using namespace std;

struct Node{
    int start, end;
};
Node node[10];
vector <pair<int,int>> v;// len, node number

int parent[10];

int Find(int idx)
{
    if(idx == parent[idx] ) return idx;
    else{
        parent[idx] = Find(parent[idx]);
        return parent[idx];
    }
}

void Union(int idx1 , int idx2)
{
    idx1 = Find(idx1);
    idx2 = Find(idx2);
    
    if(idx1 != idx2)    parent[idx2] = idx1;
    
}

int Kruskal()
{
    int ans =0;
                            
    sort(v.begin(),v.end());
    
    for(int i=0;i<v.size();i++)
    {
        int len = v[i].first;
        int idx = v[i].second;
       
        if(Find(node[idx].start) == Find(node[idx].end))    continue;
        Union(node[idx].start , node[idx].end);
        ans += len;
    }
    
    int num = Find(1);
    for(int i=2;i<=5;i++){
        if(Find(i) != num)  return -1;
    }
    return ans;
}

int main(void)
{
    for(int i=1;i<=5;i++)   parent[i]=i;
    
    node[0] = {1,2};
    node[1] = {1,3};
    node[2] = {2,3};
    node[3] = {2,5};
    node[5] = {3,5};
    node[6] = {4,5};
    node[7] = {3,4};
    node[8] = {1,4};
    
    v.push_back({10,0});
    v.push_back({4,1});
    v.push_back({7,2});
    v.push_back({13,3});
    v.push_back({2,4});
    v.push_back({42,5});
    v.push_back({33,6});
    v.push_back({5,7});
    v.push_back({17,8});
    
    Kruskal();

}