최소신장트리 MST, Kruskal(크루스칼), Prim(프림), Sollin(솔린)

최소신장트리 MST

하나의 연결성분으로 이루어진 무방향 가중치 그래프에서 간선의 가중치 합이 최소인 신장트리

※ 신장트리란(Spanning Tree)? → 주어진 그래프가 하나의 연결성분으로 구성되어 있을 때, 그래프의 모든 정점들을 싸이클 없이 연결하는 부분그래프

MST 알고리즘에는 Kruskal, Prim, Sollin이 있음→Greedy

Kruskal 알고리즘

1. 가장 작은 가중치 순서대로 선택 (가중치1→2→3 이런식으로)
2. 사이클 만들면 버리기
3. n-1개 간선 선택되면 종료

주요코드(일부)

weights=[(0,1,9),(0,2,10)...(5,6,6)] # u,v,wt 순
#kruskal은 가중치를 기준으로 정렬해야함!
weights.sort(key=lambda t:t[2])

# find함수 : u가 속한 집합의 루트를 찾는 함수
def find(u):
	if u!=p[u]:
		p[u]=find(p[u]) # 경로압축
	return p[u]

# union함수 : 2개의 집합을 하나로 합치는 함수
def union(u,v):
	root1=find(u)
	root2=find(v)
	p[root2]=root1 #root1가 root2의 부모가 되게

# 실행부분
tree_edges=0
mst_cost=0
while True:
	if tree_edges==N-1:
		break
	u,v,wt=weights.pop(0)
	if find(u)!=find(v):
		union(u,v)
		mst.append((u,v))
		mst_cost+=wt
		tree_deges+=1

Prim 알고리즘

1. 임의의 시작 정점
2. 가장 가까운 정점을 추가하여 트리를 만듦
3. 만들어진 트리에 인접한 가장 가까운 정점을 하나씩 추가

주요코드(일부)

for k in range(N):
	m=-1 # m:min_vertex
	min_value=sys.maxsize
	
	# 가장 가까운 정점찾기
	for j in range(N):
		if not visited[j] and D[j]<min_value:
			min_value=D[j]
			m=j
	visited[m]=True
	
	# 정점 m에 인접한 w와 (m,w)의 가중치 wt에 대해
	for w,wt in list(g[m]):
		if not visited[w]:
			if wt < D[w]:
				D[w]=wt
				previous[w]=m

# 비용계산
mst_cost=0
for i in range(1,N):
	mst_cost+=D[i]

 

 

Kruskal vs. Prim

Kruskal	Prim
O(MlogN)	O(N^2)
조밀 그래프일 때 좋음	희소 그래프일 때 좋음 이진힙사용→O(NlogN)

+Sollin 알고리즘

각 정점을 독립적인 트리로 보고, 각 트리에 닿아있는 간선들 중 가중치가 작은 간선 선택하여 트리 합치기

수행시간 O(MlogN)