[JS] 최소 신장 트리 (MST) - Kruskal

 

 

해당 그래프를 최소한의 비용으로 모든 정점을 연결하려면?

필요한 간선 외에는 모두 제거하면 된다.

이러한 알고리즘을 최소 신장 트리라고 한다.

 

 

✨ 최소 신장 트리 (Minimum Spanning Tree)

• 신장 트리 (Spanning tree)란 그래프 내에 모든 정점을 포함하는 최소 연결 부분 그래프이다. 
• 여기서 최소 신장 트리 (MST)는 다음과 같은 조건을 만족한다.
  • 최소한의 간선으로 모든 정점이 연결되어야 한다.
  • 모든 신장 트리 중 가중치의 값이 최소여야 한다.
  • Cycle이 발생해서는 안된다.
• 최소 신장 트리를 위한 알고리즘은 대표적으로 두 가지가 있다.
  • 크루스칼 (Kruskal)
  • 프림 (Prim)

 

 

미리 알아두면 좋은 크루스칼 알고리즘

• 그리디 개념을 이용하여 구현할 수 있다.
• 먼저 모든 그래프를 부분 집합으로 분리한다.
• 가장 가중치가 낮은 간선을 선택하고 부분 집합을 연결한다.
• 이때, Cycle이 발생하지 않도록 주의한다.
  • 공통 최상위 부모를 찾는 것으로 막을 수 있다.
  • Cycle을 판단하기 위한 알고리즘으로 Union-Find 알고리즘을 이용할 수 있다.

 

Union-Find 알고리즘

• 서로소 집합을 구하기 위한 알고리즘
  • 서로소 집합은 공통 원소가 없는 두 집합을 표현하기 위한 자료구조
• 서로 다른 두 집합을 변합하는 연산 Union과 집합의 원소가 어떤 집합에 속해 있는지 판단하는 연산 Find를 나타낸다.
• 일반적으로 트리 구조로 구성한다.
• 편의상 재귀로 구현하는 경우가 많다.

 

---

✨ Union

두 원소를 하나의 집합으로 합쳐주는 자료구조

초기에는 자기 자신을 부모 정점으로 설정한다. (자기 자신 = 자신이 속한 집합) 여기서 key는 원소, value는 자기 자신이 속한 부모 정점
B가 A에 속할 경우, B의 부모 원소를 바꿔준다. 이렇게 되면 두 원소는 같은 집합이 된다.
D가 B에 속할 경우, D의 부모를 B의 부모인 A로 지정한다. 즉, 집합의 최상위 요소를 부모로 지정한다는 뜻이다. 이제 D도 한 집합의 소속이 되었다.
E가 C에 속할 경우 E의 부모는 C가 된다.
E가 B에도 속할 경우, E의 부모를 그대로 B로 바꿔주는 것이 아니라 C와 B가 속한 집합의 최상위 원소인 A로 지정한다. 이런식으로 두 집합을 하나의 집합으로 합쳐줄 수 있다.
하지만 결과를 보면 해당 구조만으론 각 원소가 어떤 집합에 속하는지 알 수 없다. 따라서 Find 연산이 필요하다.

 

✨ Find

Find 연산의 가장 간단한 방법은, 부모 원소가 자기 자신일 때까지 올라가는 방법이다.

 

예를 들어 E가 소속된 집합의 최상위 원소를 찾을 때 C를 거처 A를 보면 최상위 원소를 알 수 있다.

만약 다른 원소와 같은 집합인지 알기 위해서는 두 원소의 최상위 원소가 같은지 보면 된다.

 

하지만 이 방식엔 한 가지 문제가 있다.

만약 편향 트리라면 시간복잡도가 O(n)이 소요된다.

 

그래서 우리는 경로 압축을 통해 이 부분에 대한 최적화가 필요하다!

 

우리가 최종 공통 부모를 찾을 때 결국 모든 경로를 탐색하게 된다.

여기서 만약 재귀로 구현했다면 돌아오면서 해당 원소를 등록하고 최상위 부모를 변경해주면 된다.

그러면 자연스럽게 경로가 최적화된다.

이렇게 최적화하면 거의 상수시간만에 공통인 부모를 찾을 수 있게 된다.

 

 

---

✨ Kruskal

데이터를 간선과 서로소 집합으로 구성한다.

여기서 탐욕적으로 탐색을 할 것이기 때문에 간선들을 정렬해 준다.

이렇게 구성하고 나면 본격적으로 크루스칼 알고리즘이 시작된다.

 

1. 가장 가중치가 낮은 간선을 선택하고 두 정점을 한 집합으로 이어준다.

아래와 같은 집합이 구성된다.

2. 다음으로 가중치가 낮은 간선인 A, B 간선을 선택하고 두 정점을 이어준다.

A, B, D가 한 집한이 된다.

 

3. 이번엔 B, C 간선을 선택한 후, 두 간선을 이어준다.

4. B, F 간선을 선택 후 두 집합을 합쳐준다.

5. 이번에는 조금 다른데, A, C 간선을 선택하고 두 정점을 합쳐주려고 하지만 사이클이 발생하는 구조이다.

여기서 두 정점 집합의 최상위 원소가 같다면 이미 같은 집합에 소속되어 있다는 뜻이기 때문에 사이클이 발생한다.

따라서 해당 간선은 패스한다.

6. 이번엔 F, G 간선을 선택한다.

이번엔 사이클이 발생하지 않기때문에 그대로 합쳐준다.

7. 이어서 D 간선을 선택한다.

여기까지 오면, 모든 정점이 간 집합으로 구성되어 있다는 걸 알 수 있다.

8. 그래도 진행을 해보자면, E, F 간선은 사이클이 발생하게 되어서 패스하게 된다.

9. 마찬가지로 C, F 간선도 패스한다.

이렇게 패스한 간선을 모두 제거하면 최소 신장 트리가 완성된다.

 

 

정리

• 가장 가중치다 낮은 간선부터 선택하는 것 = Greedy
• 각 원소가 같은 집합인지 확인하기 위한 알고리즘 = Union-Find
• 두 정점이 같은 집합에 속한다면 = Cycle

 

 

---

✨ 관련 문제 풀이

 

https://lazyhysong.tistory.com/entry/JS-Kruskal-%EC%84%AC-%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0

[JS] Kruskal - 섬 연결하기