[알고리즘] 크루스칼알고리즘

크루스칼 알고리즘이란?

그래프 내의 모든 정점들을 가장 적은 비용으로 연결 하기 위해 경로를 찾을 때 사용되는 알고리즘입니다.

즉 그래프에는 노드(node)와 엣지(edge)가 있으며 엣지에는 가중치가 포함되어 있습니다.

이러한 그래프에서 모든 정점을 포함하고 사이클(Cycle)이 없는 연결선을 그렸을 때 가중치의 합이 최소가 되는 값을 구할 때 사용합니다. 

크루스칼 알고리즘은 다음과 같은 단계로 구합니다.

• 1단계 : 각 정점 하나만을 포함하는 n개의 집합을 만듭니다.
• 2단계 : 모든 간선을 가중치 값을 기준으로 오름차순으로 정렬합니다.
• 3단계 : 가중치가 가장 작은 것 부터 검사하여 간선이 서로소(disjoint)인 두 집합을 연결하면 그 간선을 추가하고 연결된 두 집합을 하나의 집합으로 연결 합니다.
• 4단계 : 추가된 간선이 최소신장트리가 될 때까지 반복합니다.

3단계에서 두 집합을 하나의 집합으로 연결하고 두 집합이 서로소인지 판단하는 알고리즘은 유니온파인드( https://wondangcom.tistory.com/1587  ) 알고리즘으로 해결 할 수 있습니다.

다음과 같은 그래프가 있을때 처리 과정은 다음과 같습니다.

4개의 집합을 만든 다음 간선의 가중치를 기준으로 정렬해서 작은 것 부터 찾아서 연결 합니다. 1,2,3 을 연결 한 다음 v1과 v3을 가져 왔으면 두개의 노드는 같은 집합이므로 제외 하고 나머지 역시 제외 됩니다.

 

문제풀이)

정올 - 최소비용신장트리 ( http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=340&sca=3020 ) 

JUNGOL

#include <stdio.h>
#include <algorithm>
using namespace std;


struct data {
    int s, e, c;
    bool operator<(const data&r)const{
        return c<r.c;
    }
}adj[10010];

int G[101], n, cnt=1, ans;

int unionfind(int node)
{
    if(node!=G[node]) G[node]=unionfind(G[node]);
    return G[node];
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int i, j, w;

    scanf("%d", &n);
    for(i=1;i<=n;i++) {
        G[i] = i;
    }
    for(i=1;i<=n;i++) {
        for(j=1;j<=n;j++) {
            scanf("%d", &w);
            if(w==0) continue;
            adj[cnt].s = i;
            adj[cnt].e = j;
            adj[cnt].c = w;
            cnt++;
        }
    }
    sort(adj+1,adj+cnt);

    for(i=1;i<cnt;i++) {
        int s=unionfind(adj[i].s), e=unionfind(adj[i].e), c=adj[i].c;
        if(s==e) continue;
        G[e]=s;
        ans+=c;

    }
    printf("%d", ans);
    return 0;
}