[자료구조] Kruskal 알고리즘

Kruskal 알고리즘

굉장히 유명한 알고리즘이다.

최소비용신장트리(MST, Minimum Spanning Tree)를 찾는 알고리즘이다.

 

예를 들어 위와 같은 가중치 그래프가 있다고 하자.

 

Prim 알고리즘은 시작 정점이 필요했지만, Kruskal 알고리즘은 시작 정점이 필요하지 않다.

Kruskal 알고리즘은 가장 작은 가중치를 갖는 간선을 찾아 여러 개의 작은 트리로 만들어두고, 붙이는 알고리즘이다.

 

쉽게 풀어서 차근차근 이야기해 보자.

 

우선, 가장 작은 가중치인 7이 연결된 두 정점을 선택하게된다.

그리고 다음으로 작은 가중치인 10이 연결된 정점들을 묶는다.

 

그 다음으로 큰 12 를 묶는다.

Kruskal 알고리즘은 연결되지 않는 게 많을 것이다. 이상해하지 말자. 곧 연결될테니

다음으로 큰 13

 

 

13이 간선으로 선택되면서 빨간색과 초록색 묶음이 합쳐진다.

 

그 다음은 16이다.

위 방식대로 반복한다.

 

최소비용 신장트리는 모든 정점을 방문하는 것이 목적이므로 위 그림을 마지막으로 Kruskal 알고리즘은 종료된다.

 

중간중간에 간선이 포함되고 안되고의 차이가 있는 그림이 있는데, 신경쓰지 말자. 

정점에 맞추어 생각하면 된다.

 

위 내용을 코드로 구현해보자.

 

Kruskal 알고리즘

#include <stdio.h>
#include <stdlib.h>

#define V 5  // 정점의 개수
#define E 7  // 간선의 개수

// 간선 구조체
struct Edge {
    int src, dest, weight;
};

// 그래프 구조체 
struct Graph {
    struct Edge edge[E];  // 간선들을 저장
};

// 서브트리의 루트 노드를 찾음
int find(int parent[], int i) {
    if (parent[i] == i)
        return i;
    return find(parent, parent[i]);
}

// 두 서브트리를 하나로 합침
void Union(int parent[], int rank[], int x, int y) {
    int xroot = find(parent, x);
    int yroot = find(parent, y);

    if (rank[xroot] < rank[yroot])
        parent[xroot] = yroot;
    else if (rank[xroot] > rank[yroot])
        parent[yroot] = xroot;
    else {
        parent[yroot] = xroot;
        rank[xroot]++;
    }
}

// 정렬하기 위한 비교 함수
int compareEdges(const void* a, const void* b) {
    struct Edge* edgeA = (struct Edge*)a;
    struct Edge* edgeB = (struct Edge*)b;
    return edgeA->weight > edgeB->weight;
}

void KruskalMST(struct Graph* graph) {
    struct Edge result[V];  // MST에 포함된 간선들
    int parent[V];  // 부모 노드를 저장
    int rank[V];    // 서브트리의 랭크를 저장

    int e = 0;  // 결과 배열의 인덱스
    int i = 0;  // 정렬된 간선을 순차적으로 처리하기 위한 인덱스

    // 초기화
    for (int v = 0; v < V; v++) {
        parent[v] = v;
        rank[v] = 0;
    }

    // 간선들을 가중치 기준으로 정렬
    qsort(graph->edge, E, sizeof(graph->edge[0]), compareEdges);

    // 간선을 하나씩 선택하여 MST를 구성
    while (e < V - 1 && i < E) {
        struct Edge nextEdge = graph->edge[i++];

        int x = find(parent, nextEdge.src);
        int y = find(parent, nextEdge.dest);

        // 사이클을 형성하지 않는 경우에만 간선을 선택
        if (x != y) {
            result[e++] = nextEdge;
            Union(parent, rank, x, y);
        }
    }

    printf("Edge \tWeight\n");
    for (i = 0; i < e; i++)
        printf("%d - %d \t%d \n", result[i].src, result[i].dest, result[i].weight);
}

int main() {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));

    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = 2;

    graph->edge[1].src = 0;
    graph->edge[1].dest = 3;
    graph->edge[1].weight = 6;

    graph->edge[2].src = 1;
    graph->edge[2].dest = 2;
    graph->edge[2].weight = 3;

    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 8;

    graph->edge[4].src = 1;
    graph->edge[4].dest = 4;
    graph->edge[4].weight = 5;

    graph->edge[5].src = 2;
    graph->edge[5].dest = 4;
    graph->edge[5].weight = 7;

    graph->edge[6].src = 3;
    graph->edge[6].dest = 4;
    graph->edge[6].weight = 9;

    KruskalMST(graph);

    return 0;
}

 

 

실행 결과