Kruskal

크루스칼 알고리즘은 최소신장트리(Minimum Spanning Tree)를 구하는 알고리즘이다.

최소신장트리는 위의 그림과 같이 어떤 그래프가 있을 때, 각 노드들을 최소 비용으로, 트리 구조로 연결한 것을 말한다. 트리는 (노드의 수 - 1)개의 간선을 갖고, 싸이클이 생기지 않는 구조를 갖는다.

크루스칼 알고리즘의 순서는 다음과 같다.

1. 간선(Edge)을 비용이 적은 순서대로 정렬한다.

2. 정렬된 간선을 순서대로 추가하는데, 이 때 싸이클이 생기지 않도록 하는 간선만 추가한다.

3. 이를 간선의 수가 노드의 수 - 1 개가 될 때까지 반복한다.

어떤 간선을 추가했을 때 싸이클이 생기는지의 여부는 Disjoint sets(분리집합, 상호배타적집합)을 이용한다. Disjoint sets를 표현하기 위한 자료구조로 disjoint-set data structure를 이용한다. (union–find data structure, merge–find set 라고도 불린다.)

 

#include <stdio.h>
#include <malloc.h>
 
#define N 100
 
int distance[N][N];
int n;
int p[N];
int rank[N];
int sum;
 
typedef struct Edge
{
    int x, y, k;
}Edge;
 
Edge edge[N * N];
int cnt;
 
int FindSet(int x)
{
    if (p[x] == x) return x;
    else p[x] = FindSet(p[x]);
}
 
void CreateSet()
{
    for (int i = 0; i < N; i++)
    {
        p[i] = i;
        rank[i] = 0;
    }
}
 
void MergeSet(int x, int y)
{
    x = FindSet(x);
    y = FindSet(y);
 
    if (rank[x] > rank[y])
    {
        p[y] = x;
    }
    else
    {
        p[x] = y;
        if (rank[x] == rank[y]) rank[y]++;
    }
 
}
 
void Merge(Edge *arr, int left, int mid, int right)
{
    int l_idx = left;
    int r_idx = mid + 1;
    int idx = left;
    Edge *temp = (Edge *)malloc(sizeof(Edge) * (right + 1));
 
    while (l_idx <= mid && r_idx <= right)
    {
        if (arr[l_idx].k > arr[r_idx].k) temp[idx++] = arr[r_idx++];
        else temp[idx++] = arr[l_idx++];
    }
 
    while (l_idx <= mid) temp[idx++] = arr[l_idx++];
    while (r_idx <= right) temp[idx++] = arr[r_idx++];
 
    for (int i = left; i <= right; i++) arr[i] = temp[i];
    free(temp);
}
 
void MergeSort(Edge *arr, int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);
        Merge(arr, left, mid, right);
    }
}
 
int main()
{
    int i, j;
 
    //freopen("input.txt", "r", stdin);
 
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &distance[i][j]);
    
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (j > i)
            {
                edge[cnt].x = i;
                edge[cnt].y = j;
                edge[cnt++].k = distance[i][j];
            }
        }
    }
 
    MergeSort(edge, 0, cnt);
    CreateSet();
 
    i = j = 0;
    
    while (i < n - 1)
    {
        int u = FindSet(edge[j].x);
        int v = FindSet(edge[j].y);
 
        // 싸이클이 안생길 떼
        if (u != v)
        {
            MergeSet(u, v);
            sum += edge[j].k;
            i++;
        }
        j++;
    }
    printf("%d\n", sum);
 
    return 0;
}