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

하나의 연결된 그래프에서 모든 정점을 포함하면서 모든 간선의 가중치 합이 최소가 되는 트리.
여기서 가중치는 각 간선에 부여된 비용이나 거리를 의미

최소 신장 트리의 특성

1. 연결성 : 최소 신장 트리는 그래프 내의 모든 정점을 포함하며, 모든 정점 사이에 경로가 존재
2. 비용 최소화 : 간선의 가중치 합이 최소가 됨
3. 유일성 : 최소 신장 트리는 그래프에 대해 유일하지 않을 수 있지만, 가중치가 같은 경우 유일한 해가 될 수 있음.

최소 신장 트리 구하는 알고리즘

1. 크루스칼 알고리즘(Kruskal`s Algorithm)

• 간선 기반의 알고리즘으로, 가장 적은 비용의 간선부터 선택하여 신장 트리를 만들어 나감
• 모든 간선을 가중치 기준으로 오름차순 정렬
• 가장 가중치가 작은 간선부터 시작하여, 사이클을 형성하지 않으면서 트리에 추가
• 정확히 V - 1 개의 간선을 선택할 때까지 반복. (V는 정점의 수)
• 시간 복잡도는 O(E log E)

2. 프림 알고리즘(Prim`s Algorithm)

• 정점 기반 알고리즘으로, 특정 정점을 시작점으로 선택하여 해당 정점에서 연결된 간선 중 가장 작은 가중치의 간선을 선택하여 트리를 확장
• 임의의 시작 정점을 선택하여 해당 정점과 연결된 간선 중 최소 가중치의 간선을 선택하여 트리에 추가
• 트리에 포함된 정점들과 연결된 간선 중 최소 가중치의 간선을 선택하여 트리를 확장
• 모든 정점이 트리에 포함될 때까지 위 과정을 반복
• 시간 복잡도는 O((V + E)log V) 또는 O(V^2 log V)