[알고리즘] 23 Minimum Spanning Trees

문제
set of node 와 edges
edge 는 두개의 노드로 이루어짐
u,v노드를 잇는 edge 는 w(u,v) 만큼의 비용이 들어감
-> 모든 노드가 커넥되어야하고 , 최종 비용이 최소여야한다.

: kruskal' / prim's 알고리즘은 둘다 optimal solution 을 찾아낸다

G = (V,E)
weight w(u,v)
T는 스패닝 트리 스패닝 트리 E 전체집합의 부분

some properties of MST
1. |v|-1 개의 간선
2. cycle 없어야
3. 유일하지 않을 수 있다

Building up the solution
. A는 간선 없는 상태
. loop in variant 를 통해 A의 edge 를 추가해 나간다
loop in variant : loop 이전에 A는 MST의 subset 이다
. 이 invariant를 만족시키는 간선을 추가한다

GENERIC-MST(G,w)
A = 공집합
while A 가 MST의 부분집합을 만족시키지 못함
	A에 있어 안전한 (u,v)간선을 찾는다 
    A = A 합집합 {(u,v)}
return A

Loop invariant : prior to each iteraion , A is a subset of some MST

initialization : the empty set trivally satisfies the loop invariant
Maintaenance: Siince we add onle safe edge, A remains a subset of MST
Termination: All edges added to A are in and MST, so when we stop, A is spanning tree that is also an MST

Finding safe edge

: cut(S, V-s) 는 V라는 노드들을 S 집합과 V-S집합으로 나눈 partition 이다.
: edge(u,v) crosses의 의미는, S와 V-S집합의 노드들을 하나씩 걸친 간선을 의미
: 어떤 간선도 cross하지 않는다면, cut은 A를 따른다. (A는MST의 부분집합)
: light edge : cross하는 간선들중 weight가 가장 작은것

Rule for recognizing safe edges

앞선 정의에서 light edge 인 (u,v)는 A에 대해 safe 하다.

증명 :
T : A를 포함하는 MST
: T가 경량간선인 (u,v)를 포함하지 않는다는 가정

MST-KRUSKAL(G,w)
A<- 공집합
for 그래프의 각각의 정점에 대해:
	do MAKE-SET(v) ( V개의 트리를 만든다 )
E의 간선들을 가중치 w 증가순으로 정렬 
for 각각의 간선 (u,v) ( E(가중치 증가순으로 고려된다)
	do if Find-SET(u) !== Find-SET(v) 
    	then A <- A 합집합 (u,v)
        	UNION(u,v)
return A

프림 알고리즘

MST-PRIM(G, w, r) 
for 각각의 u { V[G]
	do key[u] <- 무한 ( 트리의 한정점과의 연결 간선 가중치중 최소)
    	파이[u] <- NIL ( 부모노드) 
key[r] <- 0
Q <- V[G]
while Q != 공집합
	do u <- EXTRACT-MIN(Q)
    	for 각각의 v { Adj[u]
        	do if v { Q and w(u,v) < key[v]
            	then 파이[v] <- u
                	key[v] <- w(u,v)