[그래프] 최소 신장 트리(MST, minimum spanning tree) - 1

1. 문제정의

최소 신장 트리 ( Minimum Spanning Tree )란?

최소 신장 트리( MST )란, 주어진 그래프에서 최소한의 비용으로 트리를 만드는 것을 의미합니다.

BFS , DFS는 각 규칙에 따라 모든 정점들을 연결하는 트리를 생성했었습니다.

MST도 마찬가지로 모든 정점들을 연결하는 트리를 생성하는데, 이 때 규칙은 최소한의 비용이 되는 그래프가 되도록 하는 것입니다.

 

---

2. 문제 설계

Kruskal's 알고리즘Kruskal's 알고리즘은 두 개의 트리를 연결하는 모든 간선 중 가장 작은 간선( u , v )를 찾아 MST의 부분집합에 추가합니다.
Kruskal's 알고리즘은 안전 간선을 연결할 때 Union - Find 자료구조를 이용합니다.

---

3. 구현

include <stdio.h>

#include <stdlib.h>
#include <string.h>

//간선 : 시작점, 출발점, 가중치
struct Edge{

    int src, dest, weight;
};

 
//그래프 : 정점 수, 간선 수, 간선 배열을 가리키는 포인터

struct Graph{
    int V, E;

    struct Edge* edge;
};

 
// 그래프 생성함수

struct Graph* createGraph(int V, int E) {
    struct Graph* graph = new Graph;

 graph->V = V;
    graph->E = E;

    graph->edge = new Edge[E]; //간선 수 만큼 동적할당
 

    return graph;
}

 
//집합 : root, rank

struct subset{
    int parent;

    int rank;
};

 
// i가 속한 집합을 찾는 함수

int find(struct subset subsets[], int i){
    if (subsets[i].parent != i)

        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;

}
void Union(struct subset subsets[], int x, int y){ // x와 y를 합치는 연산을 하는 함수

    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;   

 elseif (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;

    else {
        subsets[yroot].parent = xroot;

        subsets[xroot].rank++;
    }

}


int myComp(constvoid* a, constvoid* b) { //오름차순 정렬
    struct Edge* a1 = (struct Edge*)a;

    struct Edge* b1 = (struct Edge*)b;
   if(a1->weight > b1->weight) return1;

   elseif(a1->weight < b1->weight) return -1;
   else return0;

}
int KruskalMST(struct Graph* graph){

    int V = graph->V;
    struct Edge result[V];  // 결과 스패닝 트리의 간선 정보를 담는 변수

    int e = 0, i = 0, sum = 0;
    // 간선을 정렬 qsort(target, size, width, compare)

    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
    // 정점 수 만큼 집합변수 동적 할당

    struct subset *subsets =
        (struct subset*) malloc( V * sizeof(struct subset) );

    // 모든 정점에 대하여 집합변수 초기화
    for (int v = 0; v < V; ++v){

        subsets[v].parent = v;
        subsets[v].rank = 0;

    }
    while (e < V - 1){ //트리의 간선 수 = 정점 수 - 1

        // 작은 간선 선택
        struct Edge next_edge = graph->edge[i++];

        //find연산으로 해당 간선의 두 점이 같은 집합인지 판단
        int x = find(subsets, next_edge.src);

        int y = find(subsets, next_edge.dest);
        // 사이클 존재 여부 판단

        if (x != y){
            result[e++] = next_edge;

            Union(subsets, x, y);
        }

    }
    for (i = 0; i < e; ++i){

 sum += result[i].weight;
        printf("%d -- %d == %d\n", result[e].src, result[e].dest, result[e].weight);

   }

 return sum;

}


int main(){

 int V, E; //정점과 간선의 수를 담는 변수

 scanf("%d %d",&V, &E);

           struct Graph* graph = createGraph(V, E);

 for(int i = 0; i<E; i++)

 scanf("%d %d %d",&graph->edge[i].src, &graph->edge[i].dest, &graph->edge[i].weight);
 
 int result = KruskalMST(graph);
            printf("%d\n", result);
 return 0;
}

---

4. 분석

 Kruskal 알고리즘을 실행하기 위해서는 간선을 가중치 기준으로 오름차순 정렬이 필요하다. 정렬하는데 O(N*logN)만큼의 Big-O가 필요하다. 또한, 사이클 존재여부를 알기 위해서 Find-Union연산을 하는데, Find-Union의 Big-O는 정렬보다 크게 증가하는 함수가 아니기 때문에 최종 Big-O는 O(N*logN)이다. 일반적으로 O(N*logN)은 n의 최대 크기가 1,000,000일 때, 1초안에 답을 낼 수 있다. 하지만 제시된 코드는 Edge를 1차원 배열로 만들었기 때문에, 각 언어의 배열의 최대 크기를 넘을 수 없을 것이다. 따라서 1초안에 해결하는데 최대 정점 수와 간선 수의 최대 입력은 각 언어의 배열 최대 크기로 예상된다.