[Algorithm] Minimal Spanning Tree

최소 신장 트리 (Minimal Spanning Tree)

Tree 는 그래프의 한 종류로써 특정한 규칙을 따른다.

• 연결성: 트리는 모든 정점이 연결되어 있어야 한다. 즉, 어떤 두 정점을 선택해도 항상 경로가 존재한다.
• 사이클 없음: 트리는 사이클이 존재하지 않는 구조로, 한 정점에서 시작해서 다른 정점을 계속해서 방문하더라도 같은 정점으로 돌아오는 경로가 없다.

Spanning Tree (신장 트리)

주어진 그래프의 모든 정점을 포함하면서 트리의 기본 규칙을 만족하는 그래프를 의미한다.

즉, 그래프 내의 모든 정점을 포함하고 정점 간 서로 연결이 되어 사이클이 존재하지 않는 그래프

모든 정점이 포함되어 있으면서, 모든 노드는 적어도 하나의 간선으로 연결되어 있는 것을 볼 수 있다.

정점의 갯수가 n개 일 때, 신장 트리의 간선은 n-1이 되고, 연결 관계에서 사이클을 형성하지 않는다.

간선 위에 적힌 숫자는 그 간선의 가중치를 말한다.

이렇게 신장 트리들 중에서 가중치의 합이 최소가 되는 신장 트리를 최소 신장 트리(Minimum Spanning Tree, MST) 라고 한다. 위의 예시에서 가중치의 합이 가장 최소가 되는 것은 30으로 두번째 신장 트리가 최소 신장 트리가 된다.

[최소 신장 트리를 구하는 문제의 예시]

• 여러 개의 네트워크 지점들이 있는데, 모든 지점들을 유선으로 연결하면서 연결선의 총 길이가 최소가 되어야 하는 문제
• 도시들을 모두 연결하면서 연결하는 도로의 길이 합이 최소가 되어야 하는 문제

그래프에서 최소 신장 트리를 찾는 대표적인 알고리즘 2개가 있다. 첫 번째는 프림 알고리즘, 두 번째는 크루스칼 알고리즘이다.

---

프림 알고리즘 (Prim Algorithm)

프림 알고리즘은 그리디 알고리즘의 일종으로, 시작 정점에서 정점을 하나씩 추가하면서 MST를 만든다. 각 단계에서 현재까지 선택한 정점 집합에 연결된 간선 중에서 가중치가 최소인 간선에 연결된 정점을 추가하는 탐욕법을 사용한다.

• 배열로 구현할 경우 시간 복잡도 $O(V^2)$
• 우선 순위 큐로 구현할 경우 시간 복잡도 $O(E \log V)$

우선 순위 큐를 사용한 동작 과정

1. 우선 순위 큐를 생성하여 임의의 시작 정점을 (정점, 가중치) 형식으로 넣는다.
   (시작 정점의 우선순위는 0으로 설정)
2. 우선 순위 큐에서 가중치(비용)가 가장 작은 정점을 꺼낸다.
   ① 정점이 이미 MST에 포함됐다면 과정 1 로 돌아간다.
   ② 그렇지 않다면 MST 에 포함하고 계속 진행한다.
3. 정점과 연결된 간선의 정점을 찾고 아직 방문하지 하지 않았다면 우선 순위 큐에 추가한다.

우선 순위 큐가 빌때까지 과정 2, 3을 반복한다.

가장 작은 가중치 간선을 우선순위 큐에서 추출하는 연산은 $O(\log V)$ 시간이 소요된다. 간선을 고려할 때마다 우선순위 큐에서 연산이 이루어지므로, 프림 알고리즘의 전체 시간 복잡도는 $O(E \log V)$ 가 된다.

---

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

크루스칼 알고리즘은 그리디 알고리즘의 일종으로, 그래프의 간선을 하나씩 늘리며 MST를 만든다. 간선을 늘릴 때 가중치가 최소인 간선부터 추가하는 탐욕법을 사용한다.

동작과정

1. 간선 데이터를 가중치에 따라 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
   ① 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
   ② 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
3. 모든 간선에 대하여 2번의 과정을 반복한다.
4. 선택된 간선의 갯수가, 정점의 갯수-1 만큼 되면 종료한다.

동작 과정 중 2-② 에서 사이클이 발생하면 포함시키지 않고 넘어갔는데, 사이클 발생 여부를 판단할 때 Union-Find 자료구조를 사용한다.

Union-Find

• 서로소인 부분집합의 표현
  • 여러 노드가 있을 때, 두 노드가 같은 그래프에 속해있는지 알 수 있다.
  • union(x, y) 연산과 find(x) 연산으로 이루어져 있다.
    • union(x, y) : x와 y그래프를 합친다.
    • find(x) : x가 어느 그래프에 속하는지 연산한다.

union-find 알고리즘은 시간복잡도가 상수이므로 크루스칼 알고리즘의 시간복잡도는 간선들을 가중치 기준으로 정렬하는 데 걸리는 시간에 의존한다. 일반적인 경우 빠른 정렬 알고리즘의 시간복잡도는 $O(N \log N)$이므로 이 경우 크루스칼 알고리즘의 시간복잡도는 $O(E \log E)$가 된다.

---

크루스칼 알고리즘은 간선들을 가중치 기준으로 정렬하고, Union-Find 자료구조를 사용하여 사이클을 검사하고 최소 신장 트리를 구한다. 시간 복잡도는 주로 간선 정렬에 의해 결정된다.

프림 알고리즘은 우선 순위 큐를 사용하여 최소 가중치 간선을 선택하고 연결된 정점을 관리한다. 시간 복잡도는 주로 우선 순위 큐 연산에 의해 결정된다.

간선의 수가 적은 Sparse Graph 의 경우 크루스칼 알고리즘이 유리하고 간선의 수가 많은 Dense Graph의 경우 프림 알고리즘이 유리하다.

참고

https://velog.io/@suk13574/자료구조-최소-신장-트리
https://chanhuiseok.github.io/posts/algo-33/
https://velog.io/@suk13574/알고리즘Java-프림Prim-알고리즘