[c++] 크루스칼 알고리즘(Kruskal's Algorithm) 최소 신장 트리 알고리즘

08 Dec 2023

크루스칼 알고리즘은 연결된 가중치 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST)를 구성하기 위한 알고리즘 중 하나입니다.

알고리즘 개요

크루스칼 알고리즘은 탐욕 알고리즘(Greedy Algorithm)을 기반으로 하며, 다음과 같은 단계로 동작합니다:

모든 간선을 가중치를 기준으로 오름차순으로 정렬합니다.
가중치가 가장 작은 간선부터 시작하여, 사이클을 형성하지 않는 간선을 하나씩 추가합니다.
모든 정점이 연결될 때까지 위의 과정을 반복하고, 최종적으로는 최소 신장 트리를 구성합니다.

구현 예제

아래는 C++로 구현된 크루스칼 알고리즘의 간단한 예제 코드입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 간선을 표현하는 구조체
struct Edge {
    int src, dest, weight;
};

class Graph {
public:
    int V, E; // 정점 수, 간선 수
    vector<Edge> edges; // 간선 정보를 담는 벡터

    Graph(int v, int e) : V(v), E(e) {}

    // 크루스칼 알고리즘 구현
    void kruskalMST() {
        // 정점들을 서로소 집합으로 만들기 위한 배열
        vector<int> parent(V, -1);

        // 가중치를 기준으로 모든 간선을 정렬
        sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
            return a.weight < b.weight;
        });

        int edgeCount = 0, i = 0;
        while (edgeCount < V - 1) {
            Edge nextEdge = edges[i++];

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

            // 사이클을 형성하지 않는다면 해당 간선을 추가
            if (x != y) {
                cout << nextEdge.src << " - " << nextEdge.dest << endl;
                unionSet(parent, x, y);
                edgeCount++;
            }
        }
    }

    // 해당 정점이 속한 집합을 찾는 함수
    int find(vector<int>& parent, int i) {
        if (parent[i] == -1) return i;
        return find(parent, parent[i]);
    }

    // 두 정점을 하나의 집합으로 합치는 함수
    void unionSet(vector<int>& parent, int x, int y) {
        int xset = find(parent, x);
        int yset = find(parent, y);
        parent[xset] = yset;
    }
};

int main() {
    int V = 4, E = 5;
    Graph graph(V, E);
    graph.edges = { {0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4} };

    graph.kruskalMST();

    return 0;
}

마치며

크루스칼 알고리즘은 간단한 구현으로 최소 신장 트리를 찾는 데에 유용한 알고리즘입니다. 위의 예제 코드를 통해 크루스칼 알고리즘의 구현 방법을 쉽게 이해할 수 있습니다.