최소신장트리 MST

무방향 (양수) 가중치 그래프 G =(V, E)

각 edge (u, v) ∈E에 대해서 가중치 :  W(u, v)

문제 : edge들의 부분집합 T ∈ E를 찾아라

1. T에 속한 edge들에 의해 모든 정점들이 서로 연결된다

2. 가중치의 합       ∑      w(u, v) 이 최소가 되도록 한다

                         (u, v)∈ T

3.  입력 : n개의 도시 도시와 도시를 연결하는 도로비용

     문제 : 최소의 비용으로 모든 도시들이 연결되게 한다

 

 

어떤 부분집합 A에 대해 A ∪{(u, v)} 도 역시 MST의 부분집합일 경우 edge (u, v)는 A에 대해서 안전한다

generic -mst (G, W)

A <- 공집합

while A does not form a spannig tree do 

        do find an safe edge(u, v) for A

         A <- A ∪{(u, v)}

return A 

 

그래프의 정점들을 두개의 집합 S 와 V-S로 분할한 것 : cut

1. edge(u,v)에 대해서 u ∈ S 이고 v ∈V-S일때 edge(u,v)는 cross한다

2.edge들의 부분집합 A에 속한 어떤 edge이고 (S,V-S)를 cross하지않으면 컷 (S,V-S)는 A를 존중한다. respect

 

 

 크루스칼

1. edge들을 가중치의 오름차순으로 정렬 

2. edge들을 그 순서대로 하나씩 선택한다

    이미 선택된 edge들과 cycle이 형성되면 선택하지않는다

3. n-1개 edge선택되면 종료

 

MST - Kruskal (G,W)
	A <-공집합
    for each vertex v 
    	do MAKE-SET(v) //초기화
    sort the edges of E by nondecreasing order by weight w //w 순으로 오름차순 정렬
    for each edge (u,v) in nondecreasing order 
    	do FIND-SET(u) != FIND-SET(v) //FIND-SET(v): v가 속한 집합을 찾아라
        then A <- A 합집합 {(u,v)}
        UNION(u,v) // u와 v가 속한 두 집합을 하나로 합친다
  	return A

 

union find

• 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘
• 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다.
• 노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find연산으로 이루어진다.
• 트리 구조

a의부모는 a, b의부모는 b 배열로 만들기

FIND-SET (x) //x가속합 집합의 루트,부모 찾기
	if x!= p[x]
    	then p[x] <- FIND-SET(p[x])
    return p[x]

UNION(u,v)
	x <- FIND-SET(u);
	y <-FIND-SET(v);
	p[x] <- y;

2. 프림