Kruskal 알고리즘

네트워크의 모든 정점을 최소 비용으로 연결하는 해답을 구하는 것

탐욕적인 방법으로 매 순간 가장 최적의 비용인 노드를 선택하는데

동작 방법은 다음과 같다

1. 간선들의 비용을 오름차순으로 정렬한다

2. 최소 비용부터 하나씩 선택하는데 사이클을 형성하는 간선을 제외

3. 해당 간선을 현재 MST에 추가한다

사이클 생성 여부 union-find 알고리즘 사용

시간복잡도

간선들을 정렬하는데 시간복잡도가 결정된다 퀵정렬을 사용하면 O(elog2e)

희소 그래프인 경우 Kruskal알고리즘이 적합

밀집그래프인 경우 Prim이 적합

Union-Find

public int Find(int n){
    if(n == Parent[n]) return n;
    else return Parent[n] = Find(Parent[n]);
}

public boolean Union(int a, int b){
    a = Find(a);
    b = Find(b);

    if(a == b) return false;
    else{
        if(a > b) Parent[a] = b;
        else Parent[b] = a;
    }
    return true;
}