[알고리즘2] Minimum Spanning Tree(MST)

복습하기 위해 학부 수업 내용을 필기한 내용입니다.
이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다.
그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다.

▶Contents

• MST
• Greedy algorithm
• Kruskal's algorithm
• Prim's algorithm lazy version
• Prim's algorithm eager version

 

▶MST

Minimum Spanning Tree : Wegiht 합이 최소인 spanning tree

1. Tree (connected and acyclic subgraph of G)

2. Spanning tree (모든 정점 포함)

3. 간선의 weight 합이 최소

 

Brute-force 알고리즘 : 모든 가능한 spannign tree 탐색하면서 weight 비교한다.

V, E가 커질수록 너무 많은 spanning tree가 있어서 시간이 오래 걸린다.

효율적인 방법은 greedy, kruskal, prim이 있다.

 

간선 weight 모두 다르다면 MST는 단 하나이다.

하지만 weight가 같은 간선이 있다면 MST는 둘 이상이 될 수 있다.

 

 

Partition(cut) of graph G

G의 정점 중 1 ~ (v-1) 개 정점으로 이루어진 집합

 

Crossing Edge

partition과 나머지 정점들 간 연결하는 간선

 

어떤 partition에 대해서 최소 하나의 crossing edge는 반드시 MST에 포함되어야 한다.

이유는, MST에서는 모든 정점이 연결되어야 하기에, crossing edge 중 하나 이상이 연결되어야 한다.

 

어떤 partition에 대해서 weight가 최소인 crossing edge는 반드시 MST에 포함되어야 한다.

이유는, Minimum spanning tree이니까

728x90

▶Greedy algrithm

아무 간선이 포함되지 않은 상태에서 시작한다. (MST = [])

(어떤 방식으로 든) 아직 서로 연결하지 않은 partition을 찾는다.

(crossing edge 하나도 포함 안 한 partition 찾기)

crossing edge 중 weight가 가장 작은 간선을 MST에 포함한다.

총 V-1개 간선을 포함하면 종료한다.

 

즉, 한 개의 점을 기준으로 작은 간선을 찾아서 넓혀가는 방식이다.

 

그래프가 커지만 partition의 수가 매우 많아지며, 이 중 연결하지 않은 partition을 찾는 방법이 필요하다.

 

▶Kruskal's algrithm

아무 간선이 포함되지 않은 상태에서 시작한다. (MST = [])

간선을 weight의 오름차순에 따라 하나씩 검사하며 추가한다.

이때 cycle을 만들지 않는 간선이라면 MST에 추가하는 방식이다.

총 V-1개 간선을 포함하면 종료한다.

 

오름차순으로 정렬하거나 minPQ를 쓰면 ~NlogN의 시간을 소비한다.

 

MST에 포함한 정점이 V, 간선이 E라면 cycle 탐지하는 시간은?

DFS : ~V+E <= ~V - 1 => ~V

정렬한 결과에서 E개의 간선을 가지고 온다.

따라서 시간은 ~V * E

 

Union Find를 사용하면 logN의 시간을 소비하기에

정렬과 Union Find를 사용하는 방식이 효율적이다.

def mstKruskal(g): # Constructor: finds an MST and stores it
	edgesInMST = [] # 지금까지 MST에 포함한 간선 저장
	weightSum = 0 # MST에 포함한 간선의 weight 합
    
	pq = PriorityQueue()
	for e in g.edges:
		pq.put(e)
        
	uf = UF(g.V)
	while not pq.empty() and len(edgesInMST) < g.V-1:
		e = pq.get()
		if not uf.connected(e.v, e.w):
			uf.union(e.v, e.w)
			edgesInMST.append(e)
			weightSum += e.weight
            
	return edgesInMST, weightSum

Operation	1회 비용	필요한 횟수
PQ, insert	logE	E
PQ, delete min	logE	E
UF, union	logV	V
UF, connected	logV	E

2 * ElogE + VlogV + ElogV = ~ElogE (V << E)

▶Prim's algrithm

아무 간선이 포함되지 않은 상태에서 시작한다. (MST = [])

정점 0은 MST에 포함된 상태라고 본다.

MST와 나머지 정점을 연결하는 간선 중 weight가 가장 작은 간선을 MST에 추가하는 것을 반복한다.

총 V-1개 간선을 포함하면 종료한다.

 

Kruskal : 분산된 여러 덩어리 만들기.

Prim : 한 덩어리에서 계속 뻗어 나가기.

간선의 weight가 모두 다르다면 결과로 얻은 MST는 같다.

 

 

minPQ를 활용하는 방법

초기화 : 0과 인접한 간선 모두 PQ에 추가한다.

V - 1개 간선을 추가할 때까지 아래를 반복한다.

• PQ에서 weight가 가장 작은 간선 v-w를 pop
• v와 w 둘 다 MST 상에 있으면 이 간선을 무시하고 다시 pop
• v, w 중 v가 MST 상에, w가 외부에 있다고 가정
• 간선 v-w와 새 정점 w를 MST에 추가
• 새 정점 w와 인접한 간선 중 MST 외부와 연결하는 간선 모두 PQ에 추가

def mstPrimLazy(g):
	def include(v): # v를 MST에 추가 & 인접한 간선 중 MST 외부로 향하는 간선 모두 추가
		included[v] = True
		for e in g.adj[v]: 
			if not included[e.other(v)]: pq.put(e)

	edgesInMST = [] # Stores edges selected as part of the MST
	included = [False] * g.V # included[v] == True if v is in the MST
	weightSum = 0 # Sum of edge weights in the MST 
	pq = PriorityQueue() # Build a priority queue
	include(0)

	while not pq.empty() and len(edgesInMST) < g.V-1:
		e = pq.get()
		if included[e.v] and included[e.w]: continue # v-w 모두 MST 상에 있는 간선 무시
		edgesInMST.append(e)
		weightSum += e.weight
		if not included[e.v]: include(e.v) # v,w 중 아직 MST에 포함 안 한 정점과 간선 포함
		if not included[e.w]: include(e.w)
        
return edgesInMST, weightSum

Operation	1회 비용	필요한 횟수
PQ, delete min	logE	E
PQ, insert	logE	E
included[v] 확인 - cycle check	~1	E
included[v] 변경 - 새 정점 포함	~1	V

ElogE의 시간을 소비한다.

 

PQ에 v-w와 weight를 함께 추가하는 것은 Lazy Version이다.

MST와 나머지 정점을 연결하는 간선 모두 포함한다.

MST 내부를 연결하는 간선도 일부 포함한다. (기존에 추가되었으나 weight가 높아 pop 되지 않은 것)

insert, delete 비용 : ~logE

insert, delete 횟수 : ~E

 

PQ에 other(v)와 v-w, weight를 모두 추가한 Eager Version

MST에 포함되지 않은 나머지 정점별로 (한 번에 갈 수 있는 점들만) 최소 weight 간선 하나씩만 포함한다.

MST에 포함 정점에 대한 간선은 포함되지 않는다.

(이미 최소 weight 간선이 pop 되었기 때문이다.)

insert, delete 비용 : ~logV

insert, delete 횟수 : ~V

보통 V << E이므로 비용이 절감된다.

Operation	1회 비용	필요한 횟수
PQ, delete min	logV	V
PQ, insert	logV	V
PQ, decreaseKey	logV	E
included[v] 확인 - cycle check	~1	E
included[v] 변경 - 새 정점 포함	~1	V

따라서 시간은 ElogV만큼 소모된다.