크루스칼(Kruskal) 알고리즘

크루스칼 알고리즘 (Kruskal Algorithm)

MST를 구하는 알고리즘 중 하나

 

크루스칼 알고리즘을 이용하는 예시

N개의 도시가 있는데, 그래프 구조로 되어 있는 길을 모두 건설할 돈이 없어서 최소한의 비용만 투자하여 모든 도시를 어떻게든 이어주려고 합니다.

 

관련 개념

Spanning Tree: 최소한의 간선을 사용하여 모든 정점을 연결한 그래프

MST(Minimum Spanning Tree): 가중치가 있을때 최소한의 비용을 사용한 Spanning Tree. 트리이기 때문에 사이클이 존재하면 안 됨.

→ Union-Find를 이용하여 사이클 유무 판별 

 

크루스칼 알고리즘 구현 방법

1. 간선들을 저장한 후
2. 가중치를 오름차순으로 정렬
3. 간선 목록(vector, list, array 등)을 순회하면서 가중치가 작은 순으로 간선 연결
   • Union-Find를 이용하여 두 노드의 부모가 같은지 확인(Find) -> 같다면 continue, 다르면 연결(Union)

 

크루스칼 알고리즘 개념 문제

https://www.codetree.ai/missions/9/problems/minimum-spanning-tree?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드

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

using namespace std;

const int MAX_N = 10'000;

int n, m;
int uf[MAX_N+1];
vector<tuple<int,int,int> > edges; //{w, a, b}: 가중치 순으로 정렬을 위함


int myFind(int x){
    if(uf[x]==x) return x;
    return uf[x]=myFind(uf[x]);
}
void myUnion(int x, int y){
    x=myFind(x), y=myFind(y);
    if(x==y) return;
    uf[x]=y;
}

int main() {
    cin >> n >> m;
    // uf 배열 초기화
    for(int i=1; i<=n; ++i){
        uf[i]=i;
    }
    for(int i=0; i<m; ++i){
        int a, b, w;
        cin >> a >> b >> w;
        edges.push_back({w, a, b});
    }
    // 가중치를 오름차순으로 정렬(낮음->높음)
    sort(edges.begin(), edges.end());

    int mstWeight=0;
    for(auto e : edges){
        int w, a, b;
        tie(w, a, b)=e;
        if(myFind(a)==myFind(b)) continue;
        mstWeight+=w;
        myUnion(a, b);
    }

    cout << mstWeight << '\n';
    return 0;
}