최소 신장 트리 (크루스칼, 프림 알고리즘)

최소 신장 트리(Minimum Spanning Tree, MST)는 그래프 내의 모든 정점을 최소한의 간선 비용으로 연결하는 트리를 의미합니다. 이때, 간선의 가중치 합이 최소가 되어야 합니다. 최소 신장 트리를 찾기 위한 대표적인 알고리즘으로는 크루스칼 알고리즘과 프림 알고리즘이 있습니다. 이번 글에서는 이 두 가지 알고리즘에 대해 설명하고, Java와 C로 각각 구현해 보겠습니다.

최소 신장 트리의 개념

신장 트리란, 그래프의 모든 정점을 연결하되 사이클이 존재하지 않는 부분 그래프를 의미합니다. 최소 신장 트리는 그 중에서도 모든 정점을 연결하는 비용이 최소가 되는 신장 트리입니다. 네트워크 연결, 도로 계획 등의 문제에서 최소 신장 트리를 활용할 수 있습니다.

크루스칼 알고리즘

크루스칼 알고리즘은 간선 중심의 접근 방식을 사용하여 최소 신장 트리를 구성합니다. 간선을 가중치 순으로 정렬한 후, 사이클을 형성하지 않는 간선을 하나씩 선택하여 신장 트리에 포함시킵니다. 대표적인 자료 구조로는 서로소 집합(Union-Find)을 사용하여 사이클 여부를 판단합니다.

크루스칼 알고리즘 구현 (Java)

import java.util.*;

class Edge implements Comparable<Edge> {
    int src, dest, weight;

    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    public int compareTo(Edge compareEdge) {
        return this.weight - compareEdge.weight;
    }
}

class Subset {
    int parent, rank;
}

public class KruskalMST {
    int V, E;
    Edge[] edges;

    KruskalMST(int v, int e) {
        V = v;
        E = e;
        edges = new Edge[E];
    }

    int find(Subset[] subsets, int i) {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);
        return subsets[i].parent;
    }

    void union(Subset[] subsets, int x, int y) {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);

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

    void kruskalMST() {
        Edge[] result = new Edge[V];
        int e = 0;
        int i = 0;
        Arrays.sort(edges);

        Subset[] subsets = new Subset[V];
        for (i = 0; i < V; ++i) {
            subsets[i] = new Subset();
            subsets[i].parent = i;
            subsets[i].rank = 0;
        }

        i = 0;
        while (e < V - 1) {
            Edge nextEdge = edges[i++];
            int x = find(subsets, nextEdge.src);
            int y = find(subsets, nextEdge.dest);

            if (x != y) {
                result[e++] = nextEdge;
                union(subsets, x, y);
            }
        }

        System.out.println("Following are the edges in the constructed MST");
        for (i = 0; i < e; ++i)
            System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
    }

    public static void main(String[] args) {
        int V = 4;
        int E = 5;
        KruskalMST graph = new KruskalMST(V, E);

        graph.edges[0] = new Edge(0, 1, 10);
        graph.edges[1] = new Edge(0, 2, 6);
        graph.edges[2] = new Edge(0, 3, 5);
        graph.edges[3] = new Edge(1, 3, 15);
        graph.edges[4] = new Edge(2, 3, 4);

        graph.kruskalMST();
    }
}

크루스칼 알고리즘 구현 (C)

#include <stdio.h>
#include <stdlib.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 = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));
    return graph;
}

struct Subset {
    int parent;
    int rank;
};

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) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

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

int compareEdges(const void* a, const void* b) {
    struct Edge* a1 = (struct Edge*)a;
    struct Edge* b1 = (struct Edge*)b;
    return a1->weight > b1->weight;
}

void KruskalMST(struct Graph* graph) {
    int V = graph->V;
    struct Edge result[V];
    int e = 0;
    int i = 0;

    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), compareEdges);

    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 && i < graph->E) {
        struct Edge next_edge = graph->edge[i++];
        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);
        }
    }

    printf("Following are the edges in the constructed MST\n");
    for (i = 0; i < e; ++i)
        printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
}

int main() {
    int V = 4;
    int E = 5;
    struct Graph* graph = createGraph(V, E);

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

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

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

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

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

    KruskalMST(graph);

    return 0;
}

프림 알고리즘

프림 알고리즘은 정점 중심의 접근 방식을 사용하여 최소 신장 트리를 구성합니다. 시작 정점에서부터 출발하여 신장 트리를 확장해 나가며, 항상 가중치가 가장 작은 간선을 선택하여 트리에 포함시킵니다. 큐 자료 구조와 우선순위 큐를 사용하여 효율적으로 구현할 수 있습니다.

프림 알고리즘(Prim's Algorithm) Java 구현

import java.util.*;

class Prim {
    private static class Edge implements Comparable<Edge> {
        int dest, weight;

        Edge(int dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }

        public int compareTo(Edge other) {
            return this.weight - other.weight;
        }
    }

    public static void primMST(int[][] graph) {
        int V = graph.length;
        boolean[] visited = new boolean[V];
        PriorityQueue<Edge> pq = new PriorityQueue<>();

        // 시작 노드 0에서 시작
        visited[0] = true;
        for (int i = 0; i < V; i++) {
            if (graph[0][i] != 0) {
                pq.add(new Edge(i, graph[0][i]));
            }
        }

        int mstWeight = 0;
        System.out.println("Minimum Spanning Tree (MST) 간선:");

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();

            if (visited[edge.dest]) continue;

            visited[edge.dest] = true;
            mstWeight += edge.weight;
            System.out.println("Edge: " + edge.dest + " - Weight: " + edge.weight);

            for (int i = 0; i < V; i++) {
                if (!visited[i] && graph[edge.dest][i] != 0) {
                    pq.add(new Edge(i, graph[edge.dest][i]));
                }
            }
        }

        System.out.println("MST 총 가중치: " + mstWeight);
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 2, 0, 6, 0},
            {2, 0, 3, 8, 5},
            {0, 3, 0, 0, 7},
            {6, 8, 0, 0, 9},
            {0, 5, 7, 9, 0}
        };

        primMST(graph);
    }
}

프림 알고리즘(Prim's Algorithm) C 구현

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define V 5 // 정점 개수

int minKey(int key[], bool mstSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (!mstSet[v] && key[v] < min)
            min = key[v], min_index = v;
    return min_index;
}

void printMST(int parent[], int graph[V][V]) {
    printf("Minimum Spanning Tree (MST) 간선:\n");
    int mstWeight = 0;
    for (int i = 1; i < V; i++) {
        printf("Edge: %d - %d  Weight: %d\n", parent[i], i, graph[i][parent[i]]);
        mstWeight += graph[i][parent[i]];
    }
    printf("MST 총 가중치: %d\n", mstWeight);
}

void primMST(int graph[V][V]) {
    int parent[V]; 
    int key[V];
    bool mstSet[V];

    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < V; v++)
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }

    printMST(parent, graph);
}

int main() {
    int graph[V][V] = {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0}
    };

    primMST(graph);
    return 0;
}

입출력 예시

Minimum Spanning Tree (MST) 간선:
Edge: 1 - Weight: 2
Edge: 2 - Weight: 3
Edge: 4 - Weight: 5
Edge: 3 - Weight: 6
MST 총 가중치: 16

결론

이번 글에서는 최소 신장 트리를 찾기 위한 대표적인 두 알고리즘, 크루스칼과 프림 알고리즘에 대해 알아보았습니다. 크루스칼 알고리즘은 간선 중심 접근 방식을, 프림 알고리즘은 정점 중심 접근 방식을 사용합니다. 각각의 알고리즘은 상황에 따라 더 적합하게 사용할 수 있으므로, 문제의 특성에 맞는 알고리즘을 선택하는 것이 중요합니다.

Java와 C로 크루스칼 알고리즘을 구현하면서 최소 신장 트리의 기본적인 개념과 구현 방식을 이해하는 데 도움이 되었기를 바랍니다.