최소신장트리
최소 신장 트리(Minimum Spanning Tree, MST)는 가중치가 있는 무향 그래프에서 모든 정점을 포함하는 최소 가중치 트리를 의미한다. MST는 여러 실제 문제(예: 네트워크 설계, 클러스터링)에서 중요하게 사용된다.
🔍 MST 알고리즘
MST를 찾기 위한 대표적인 알고리즘으로는 Kruskal과 Prim이 있다.
🅰 Kruskal 알고리즘
간선을 가중치 오름차순으로 정렬한 후, 사이클을 형성하지 않는 간선을 추가하여 MST를 구축.
- 간선을 가중치의 오름차순으로 정렬한다.
- 가장 작은 가중치의 간선부터 시작하여, 사이클을 형성하지 않으면 트리에 추가한다.
- 모든 정점이 포함될 때까지 이 과정을 반복한다.
- 그리디 알고리즘으로 분류되기도 함.
def find_parent(parent, a):
# 주어진 노드 a의 루트 노드를 찾는 함수 (경로 압축 기법 사용)
if parent[a] != a:
parent[a] = find_parent(parent, parent[a])
return parent[a]
def union_parent(parent, a, b):
# 두 노드 a와 b를 연결하여 같은 집합으로 만드는 함수 (Union by Rank)
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
input = sys.stdin.readline
# 정점(v)과 간선(e)의 개수를 입력받음
v, e = map(int, input().split())
# 부모 테이블 초기화
parent = [0] * (v + 1)
# 부모 테이블에서 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
# 간선 리스트와 결과 변수 초기화
edges = []
result = 0
# 모든 간선 정보 입력받기
for _ in range(e):
a, b, cost = map(int, input().split())
edges.append((a, b, cost))
# 간선을 비용 순으로 정렬
edges.sort(key=lambda x: x[2])
# 간선을 하나씩 확인하며 사이클을 생성하지 않는 경우에만 최소 신장 트리에 포함
for a, b, cost in edges:
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
# 최소 신장 트리의 총 비용 출력
print(result)🅱 Prim 알고리즘
임의의 정점에서 시작하여 인접한 최소 가중치 간선을 선택하면서 MST를 확장.
- 임의의 정점에서 시작한다.
- 현재 트리에 인접한 정점들 중에서 최소 가중치의 간선을 선택하여 트리에 추가한다.
- 모든 정점이 포함될 때까지 이 과정을 반복한다.
import heapq
def prim(graph, start):
# 최소 신장 트리를 저장할 리스트와 방문한 정점을 추적할 집합 초기화
mst = []
visited = set()
# 시작 정점으로부터의 간선을 저장하는 최소 힙 초기화
# (간선의 가중치, 현재 정점, 이전 정점)
min_heap = [(0, start, None)]
while min_heap:
# 최소 가중치 간선을 힙에서 추출
weight, u, prev = heapq.heappop(min_heap)
# 정점 u가 방문되지 않은 경우에만 처리
if u not in visited:
visited.add(u) # 정점 u를 방문 처리
if prev is not None:
mst.append((prev, u, weight)) # MST에 간선 추가
# 현재 정점 u에 연결된 모든 간선을 검사
for v, w in graph[u]:
if v not in visited:
# 방문하지 않은 정점 v로의 간선을 최소 힙에 추가
heapq.heappush(min_heap, (w, v, u))
return mst # 최소 신장 트리 반환
# 주어진 그래프의 인접 리스트 표현
graph = {
'A': [('B', 4), ('C', 4)],
'B': [('A', 4), ('C', 2), ('D', 6)],
'C': [('A', 4), ('B', 2), ('D', 8), ('E', 1)],
'D': [('B', 6), ('C', 8), ('E', 5), ('F', 3)],
'E': [('C', 1), ('D', 5), ('F', 7)],
'F': [('D', 3), ('E', 7)]
}
# Prim 알고리즘을 사용하여 최소 신장 트리를 찾기 시작하는 정점 'A'
mst = prim(graph, 'A')
print("Minimum Spanning Tree:", mst)✅ MST 알고리즘 비교: Kruskal vs Prim
| 구분 | Kruskal 알고리즘 | Prim 알고리즘 |
|---|---|---|
| 작동 방식 | 간선을 오름차순으로 정렬하고, 사이클을 형성하지 않는 간선을 선택 | 특정 정점에서 시작하여, 인접한 최소 가중치의 간선을 선택하여 확장 |
| 초기화 | 모든 간선을 오름차순으로 정렬 | 임의의 정점에서 시작 |
| 데이터 구조 | 간선 리스트, 유니온-파인드(Disjoint Set) 사용 | 우선순위 큐(최소 힙), 인접 리스트 사용 |
| 시간 복잡도 | O(E log E) (간선의 정렬) + O(E log V) (유니온-파인드) | O(V^2) (인접 행렬 사용 시) 또는 O(E log V) (인접 리스트 사용 시) |
| 적용 그래프 | 희소 그래프(간선이 적은 그래프)에 유리 | 밀집 그래프(간선이 많은 그래프)에 유리 |
| 사이클 검사 | 유니온-파인드로 사이클 검사 | 사이클 검사를 직접 하지 않음 |
| 특징 | 간선 중심 접근 | 정점 중심 접근 |
| 알고리즘 특성 | 간선을 하나씩 추가하며 MST를 구성 | 트리를 확장해가며 MST를 구성 |
| 구현 복잡도 | 비교적 간단하며, 이해하기 쉬움 | 구현이 복잡할 수 있으나, 특정 경우 더 효율적일 수 있음 |
💻 빈출 예제
🅰 크루스칼(Kruskal)
1. 정렬된 간선 목록을 이용한 MST 찾기
주어진 간선 목록을 가중치에 따라 정렬한 후 크루스칼 알고리즘을 적용하여 MST를 찾으시오.
-> 간선의 가중치를 기준으로 정렬하고 사이클을 피하면서 최소 간선을 선택
2. 사이클 검사를 포함한 MST 찾기
간선을 추가할 때 사이클이 생기는지 확인하면서 크루스칼 알고리즘을 적용하여 MST를 구하시오.
-> 사이클 검사를 위한 분리 집합(Union-Find) 자료구조를 활용
3. 주어진 노드와 간선을 통한 MST 찾기
그래프의 노드와 간선 정보가 주어졌을 때 크루스칼 알고리즘으로 MST를 구하시오.
-> 전체 그래프 정보를 바탕으로 가중치를 기준으로 정렬하고 MST를 찾기
🅱 프림(prim)
1. 시작 노드를 지정한 MST 찾기
주어진 시작 노드에서 시작하여 프림 알고리즘을 적용하여 MST를 찾으시오.
-> 특정 시작 노드에서 시작하여 가장 낮은 가중치를 가진 간선을 선택하며 트리를 확장
2. 우선순위 큐를 사용한 MST 찾기
우선순위 큐를 사용하여 가장 낮은 가중치를 가진 간선을 선택하며 프림 알고리즘을 적용하여 MST를 구하시오.
-> 우선순위 큐를 사용하여 효율적으로 최소 간선을 선택
3. 인접 행렬을 사용한 MST 찾기
주어진 인접 행렬을 사용하여 프림 알고리즘을 적용하여 MST를 찾으시오.
-> 그래프를 인접 행렬 또는 인접 리스트로 표현하고 이를 이용하여 MST를 찾기
