[c++] 크루스칼 알고리즘

08 Dec 2023

크루스칼 알고리즘은 최소 신장 트리를 찾는데 사용되는 그래프 이론 알고리즘 중 하나입니다. 최소 신장 트리는 주어진 가중치가 있는 그래프에서 모든 정점을 포함하면서 사이클을 포함하지 않는 부분 그래프 중에서 가중치의 합이 최소인 것을 말합니다.

알고리즘 동작 방식

간선의 가중치를 기준으로 오름차순 정렬합니다.
정렬된 간선 리스트에서 가장 작은 가중치를 가진 간선부터 선택합니다.
선택한 간선이 사이클을 생성하지 않는 경우에만 해당 간선을 최소 신장 트리의 일부로 추가합니다.
위 과정을 반복하여 모든 정점이 최소 신장 트리에 속할 때까지 진행합니다.

예시 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int src, dest, weight;
};

struct Graph {
    int V, E;
    vector<Edge> edges;
    
    void addEdge(int src, int dest, int weight) {
        edges.push_back({src, dest, weight});
    }
    
    vector<Edge> kruskalMST() {
        vector<Edge> result;
        // TODO: 구현 필요
        return result;
    }
};

int main() {
    Graph graph;
    // TODO: 그래프 초기화 및 간선 추가
    
    vector<Edge> mst = graph.kruskalMST();
    
    // 최소 신장 트리의 간선 출력
    for (Edge edge : mst) {
        cout << edge.src << " - " << edge.dest << " : " << edge.weight << endl;
    }
    
    return 0;
}

참고 자료

위키백과, “크루스칼 알고리즘”
C언어로 쉽게 풀어쓴 알고리즘, 문병로, 생능출판사, 2017