•
MST : Minimum Spanning Tree
•
그리디 알고리즘을 사용하는 대표적인 트리 형태의 알고리즘
최소 신장 트리란?
•
신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장트리
•
간선의 가중치를 고려해 최소 비용의 신장 트리를 선택
◦
모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것
신장트리란?
다음 조건들을 만족하는 그래프 :
1.
모든 정점이 간선으로 연결
2.
간선 개수가 정점 개수보다 하나 적은 그래프(트리니까)
3.
사이클 포함 X
최소 신장 트리의 특징
•
간선의 가중치 합이 최소
•
n개의 정점을 가지는 그래프 → n-1개의 간선만 사용
•
사이클 포함 X
•
최소신장트리는 하나가 아닐 수도 있음
최소 신장 트리 사용 사례
통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우
•
도로 건설 : 도시들을 모두 연결하면서 도로 길이가 최소가 되도록 할 때
•
전기 회로 : 단자들을 모두 연결하면서 전선 길이가 최소가 되도록 할 때
•
통신 : 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성할 때
•
배관 : 파이프를 모두 연결하면서 파이프 총 길이가 최소가 되도록 연결할 때
최소 신장 트리 구현 방법
방법 1 : Prim Algorithm
1.
임의 정점을 하나 선택해서 최소 신장 트리에 추가
2.
최소 신장 트리와 연결되어 있는 정점 중 가장 가중치가 적은 정점을 최소 신장 트리에 추가(단, 순환을 형성하지 않는 정점을 추가해야함)
3.
과정2를 신장 트리 조건에 만족할 때까지 반복
코드로 확인해볼까요?
# 우선순위 큐(힙) 사용 : 한 정점에서 시작 -> 가장 적은 비용의 간선을 선택하며 확장
import heapq
def prim_mst(v, graph, start = 1):
visited = [False] * (v+1)
min_heap = []
heapq.heappush(min_heap, (0,start)) # (가중치, 시작노드)
total_cost = 0
mst = []
while min_heap:
cost, node = heapq.heappop(min_heap)
if visited[node]:
continue
visited[node] = True
total_cost += cost
for neighbor, weight in graph[node]:
if not visited[neighbor]:
heapq.heappush(min_heap, (weight, neighbor))
mst.append((node, neighbor, weight))
return (total_cost, mst)
v = 4
graph = {
1: [(2, 1), (3, 3)],
2: [(1, 1), (3, 2)],
3: [(1, 3), (2, 2), (4, 4)],
4: [(3, 4)]
}
cost, mst_edges = prim(v, graph)
print("Total Cost:", cost)
print("MST Edges:", mst_edges)
Python
복사
방법 2 : Kruskal’s Algorithm
1.
그래프의 모든 간선을 가중치 기준으로 오름차순 정렬
2.
가중치가 낮은 간선부터 최소 신장 트리에 하나씩 추가(단, 사이클 형성 X)
3.
과정2를 신장 트리 조건에 만족할 때까지 반복
코드로 확인해볼까요?
def kruskal_mst(v, edges):
parent = [i for i in range(v+1)] # 부모 노드 초기화
def find(x):
# 초기화할 때는 자기 자신을 부모노드로 하기 때문에, 아니라면 찾아내기
if parent[x] != x:
parent[x] = find(parent[x]) # 경로 압축
# x의 부모노드 번호 반환
return parent[x]
def union(a,b):
a_root = find(a)
b_root = find(b)
if a_root != b_root:
if a_root < b_root:
parent[b_root] = a_root
else:
parent[a_root] = b_root
# 가중치 기준 오름차순 정렬
edges.sort(key=lambda x: x[2])
total_cost = 0
mst = []
for a,b,cost in edges:
# 사이클이 아닌 경우 -> 두 노드를 연결하고, 가중치를 더하고, MST 간선에 추가
if find(a) != find(b):
union(a,b)
total_cost += cost
mst.append((a,b,cost))
return total_cost, mst
v = 4
edges = [
(1, 2, 1),
(1, 3, 3),
(2, 3, 2),
(3, 4, 4)
]
cost, mst_edges = kruskal_mst(v, edges)
print("Total Cost:", cost)
print("MST Edges:", mst_edges)
Python
복사
참고자료
