크루스칼(Kruskal) 알고리즘

Kruskal 알고리즘이란?

Prim 알고리즘이 정점을 선택하면서 MST를 찾는 알고리즘이라면, Kruskal 알고리즘은 간선을 선택하면서 MST를 찾는 알고리즘이다.

알고리즘 동작 방식

1) 모든 간선을 가중치에 따라 오름차순으로 정렬한다.

2) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다. (사이클이 존재하면 다음으로 가중치가 낮은 간선 선택)

3) N-1개의 간선이 선택될 때 까지 2번을 반복한다.

• 사이클 여부는 Union-find를 사용해서 판단한다.
  
  ex) 0-1-2가 이어져 있는 상태에서 0-3 선택
  => 0-1-2 집합과 3은 다른 집합이기 때문에 선택 가능
  
  ex) 0-1-2가 이어져 있는 상태에서 0-2 선택
  => 0-1-2 집합과 2는 같은 집합이기 때문에 선택 불가능

코드

🤚 참고사항

• 아래 코드는 동작 순서를 기술하였을 뿐 특정 언어의 문법에 종속되지 않는 수도코드 입니다.

• union-find 알고리즘을 이용하여 구현하였습니다.

struct edge_type {
    int u;
    int v;
    int cost;
};

edge_type EdgeArr[max_n * (max_n - 1) / 2];  // 무방향 그래프에서 가질 수 있는 노드의 최대 개수
int edgeCnt;
int parent[max_n};

int kruskal() {
    sort(edgeArr) // cost로 오름차순 정렬
    for(int i = 0; i < n; i++) { // make set (처음에는 자기 자신이 집합이 됨)
        parent[i] = i;
    }
	
    int sumCost = 0;
    int selectCnt = 0;
    for(int i = 0; i < edgeCnt; i++) {
        int u = edgeArr[i].u
        int v = edgeArr[i].v;
        if(findSet(u) == findSet(v)) continue; // Cycle
		
        parent[findSet(u)] = findSet(v); // Union
		
        sumCost += edgeArr[i].cost;
        if(++selectCnt >= n - 1) break; // n-1개 선택했다면 끝
}

시간복잡도

👉 O(E * logE)
union-find 알고리즘을 이용하면 Kruskal 알고리즘의 시간 복잡도는 간선들을 정렬하는 시간에 좌우된다.