[Algorithms] 최소 신장 트리 (Minimum Spanning Tree)

https://www.geeksforgeeks.org/what-is-minimum-spanning-tree-mst/

What is Minimum Spanning Tree (MST) - GeeksforGeeks

---

신장 트리(Spanning Tree)란?

신장 트리는 모든 노드가 트리의 일부인 비순환 트리를 형성하는 그래프의 간선의 부분 집합이다.

신장 트리 특성

• 그래프와 싡아 트리의 정점의 수는 같다.
• 신장 트리에는 정점의 초 개수보다 하나 적은 고정된 개수의 간선이 있다.
• 신장 트리는 분리되어서는 안 된다.
• 신장 트리는 사이클이 없어야 한다.
• 신장 트리의 총 비용은 신장 트리의 모든 간선의 가중치의 합이다.
• 그래프에는 여러 개의 신장 트리가 있을 수 있다.

최소 신장 트리(Minimum Spanning Tree, MST)란?

최소 신장 트리는 가능한 모든 신장 트리 중 가중치가 가장 작은 신장 트리를 말한다. 최소 신장 트리는 가능한 모든 신장 트리 중 가능한 가장 최소 가중치를 가진다는 제약이 있으며, 모든 신장 트리의 특성을 가진다.

신장 트리와 같이 그래프에 대한 가능한 MST는 여러 개가 있을 수 있다.

크루스칼 알고리즘(Kruskal's Algorithm)

연결된 무방향 그래프에서 최소 신장 트리를 찾는 데 널리 쓰이는 알고리즘 중 하나이며, 그리디 알고리즘(Greedy algorithm)이다. 이 알고리즘은 다음과 같이 수행한다.

1. 가중치에 대해 그래프의 간선을 오름차순으로 정렬한다.
2. 신장 트리를 찾으며 반복한다.
3. 가장 작은 가중치의 간선을 추가해서 순환을 형성하지 않을 때까지 간선을 선택한다.

그래프의 연결된 구성 요소를 추적하기 위해 Disjoint-SET 자료 구조를 사용하여 효율적으로 구현할 수 있다. 크루스칼 알고리즘은 네트워크 설계, 클러스터링, 데이터 분석과 같은 다양한 실용적인 응용 분야에 사용된다.

프림 알고리즘(Prim's Algorithm)

프림 알고리즘도 그리디 알고리즘이다. 크루스칼 알고리즘과 마찬가지로 연결된 무방향 그래프에서 사용한다. 이 알고리즘은 다음과 같이 수행한다.

1. 임의의 정점을 선택하여 시작하고 MST에 이를 추가한다.
2. MST의 하나의 정점과 아직 MST에 없는 정점을 연결하는 가장 작은 가중치를 갖는 간선을 반복적으로 확인한다.
3. MST에 모든 정점이 포함될 때까지 위 과정을 계속한다.

각 반복에 대한 가장 작은 가중치를 갖는 간선을 효율적으로 선택하기 위해 우선순위 큐를 사용한다. 또한 동시에 저장하는 데이터 타입을 고려할 때 적합한 다른 자료 구조나 배열을 사용하여 MST를 추적한다.