[최소신장트리] 크루스칼(Kruskal) 알고리즘

🍀 목차
크루스칼 알고리즘
같은 목적을 가진 알고리즘
기본 이해
구현(JavaScript)
시간 복잡도

 

크루스칼 알고리즘

• 최소 신장 트리 (MST : Minimum Spanning Tree) 알고리즘 중 하나.

MST(Minimum Spanning Tree)
 모든 정점을 잇는 최소 비용 Spanning Tree를 찾는 것이 목적. 무향 가중치 그래프에서 적용한다.
사이클이 포함되어서는 안 된다(트리는 사이클 없이 모든 정점이 연결되어 있는 그래프 자료구조).

• 기본적으로 그리디 알고리즘을 바탕으로 하고 있다.
  • 항상 최소 비용을 찾고 탐욕적으로 선택한다.
• 간선 선택 기반 알고리즘이다. 간선을 가중치(비용) 오름차순으로 정렬하고 Union-Find 알고리즘을 적용하며 사이클 형성 유무를 판단하며 선택해 간다.
• 정점의 개수에 비해 간선의 개수가 적은 희소 그래프에 적용한다.

같은 목적을 가진 알고리즘

• BFS(너비 우선 탐색), DFS(깊이 우선 탐색) : 기본적으로 Spanning Tree는 연결 그래프이므로 BFS와 DFS로도 구현이 가능하다. Minumum이라는 제한이 있다면 시간 복잡도 개선을 위해 우선순위 큐(최소 힙) 등의 알고리즘을 결합하여 사용한다.
• 프림(Prim) : 그리디 기반, 정점 선택 기반 알고리즘. 임의 정점을 선택, 인접 정점에서 최소 비용을 가지는 정점을 선택해 가며 트리의 Depth를 늘려나간다. 크루스칼은 간선을 기준으로 정렬하기에 희소 그래프가 적절하나, 프림은 정점을 기준으로 확장해 가기에 정점의 개수에 비해 간선의 개수가 많은 밀집 그래프에 적합하다.
  • 시간 복잡도
    • 최소 힙을 사용하는 경우 : 정점이 V개라면, 정점 탐색 과정에서 O(V(모든 정점)* logV  = VlogV)이고 간선이 E개라면, 간선을 최소 힙에 최대 E번 추가하여 내부 정렬을 수행하니 최대 O(ElogV)이다(보통 간선이 정점보다 많기 때문이다). 
    • 배열을 사용하는 경우 : 정점마다 타 정점 탐색. O(V^2)

기본 이해

프로그래머스의 섬 연결하기 문제로 크루스칼 알고리즘을 이해해보자.

 크루스칼 알고리즘은 다음과 같은 순서로 실행된다. 위의 무향 가중치 그래프에서 모든 정점을 잇는 최소 비용을 얻고 싶다.

 

 

1. 그래프의 가중치들을 오름차순 정렬한다.  

[ [ 0, 1, 1 ], [ 1, 3, 1 ], [ 0, 2, 2 ], [ 1, 2, 5 ], [ 2, 3, 8 ] ]

 

2. 사이클 검증을 위해 Union-Find 알고리즘을 구현한다.

유니온-파인드 게시글을 기반으로 구현했다.

 

3. (반복) 적은 가중치 순서대로 Union-Find 알고리즘으로 사이클 여부를 판단하며 연결해간다.

 

- 1번째

parent = [0,1,2,3]

[ 0, 1, 1 ] 👉 0번 섬과 1번 섬을 연결하는 비용은 1.

 

find과정을 통해 두 섬의 root를 확인했을 때,

parent[0] = 0 자기 자신이 root

parent[1] = 1 자기 자신이 root

이므로, root가 더 작은 0번 섬으로 1번 섬을 합친다.

 

parent = [0,0,2,3]

정답(answer)에 cost인 1을 더한다.

answer : 1

 

- 2번째

[ 1, 3, 1 ] 👉 1번 섬과 3번 섬을 연결하는 비용은 1.

 

find과정을 통해 두 섬의 root를 확인했을 때,

parent[1] = 0

parent[3] = 3 자기 자신이 root

이므로, root가 더 작은 0번 섬으로 3번 섬을 합친다.

 

parent = [0,0,2,0]

정답에 cost인 1을 더한다.

answer : 1 + 1 = 2

 

- 3번째

[ 0, 2, 2 ]

parent = [0,0,0,0]

answer : 2 + 2 = 4

 

- 4번째

[ 1, 2, 5 ]

parent[1] = 0

parent[2] = 0

 

두 섬을 잇는 다면 사이클이 발생하게 된다. 무시한다.

 

- 마지막

[ 2, 3, 8 ]

parent[2] = 0

parent[3] = 0

 

두 섬을 잇는 다면 사이클이 발생하게 된다. 무시한다.

 

선택된 간선들

 

최소 비용은 4이다.

구현(JavaScript)

function solution(n, costs) {
  const parent = Array(n)
    .fill(0)
    .map((_, idx) => idx);
  let answer = 0;

  const find = (x) => {
    if (parent[x] === x) {
      return x;
    }
    const currentParent = find(parent[x], parent);
    parent[x] = currentParent;

    return currentParent;
  };

  const union = (A, B) => {
    const rootA = find(A, parent);
    const rootB = find(B, parent);

    if (rootA === rootB) {
      return false;
    }

    rootA < rootB ? (parent[rootB] = rootA) : (parent[rootA] = rootB);
    return true;
  };

  costs.sort((a, b) => a[2] - b[2]);

  costs.forEach((curr) => {
    const [a, b, cost] = curr;
    if (union(a, b)) {
      answer += cost;
    }
  });

  return answer;
}

시간 복잡도

$$ O(ElogE) $$

 

 간선(E)들 정렬에 퀵 정렬(O(ElogE))을 사용한다면 O(ElogE)이 된다.

📌 Union-Find 알고리즘 최적화 여부, 정렬 알고리즘의 시간 복잡도에 따라 달라질 수 있다. 

 

---

참고자료

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html