[알고리즘] 최소신장트리 (작성중)

# 가중 그래프

: 간선에 가중치 (weight)를 가지는 그래프

예) 거리, 비용, 시간

 

 

# 최소신장트리

- 신장 부그래프 : 그래프의 모든 정점들을 포함하는 부그래프

- 신장트리 : 트리인 신장 부그래프

- 최소신장트리(Minumum Spanning Tree, MST) : 간선 무게가 최소인 신장트리 

 

# 최소신장트리의 속성

## 1. 사이클 속성

T: 가중그래프 G의 최소신장트리
e: 최소신장트리 T에 존재하지 않는 G의 간선
C: e를 T에 추가하여 형성된 사이클

 

=> C의 모든 간선 f에 대해, weight(f) <= weight(e)

 

 

## 2. 분할 속성

부분집합 U, V : 가중 그래프 G의 정점들을 두 개의 부분집합
간선 e: 분할을 가로지르는 최소 무게의 간선

 

-> e를 포함하는 최소신장트리가 반드시 존재 

 

 

 

 

 

---

# 탐욕법 (그리디)

### [ 요소 ]

1. 구성: 다양한 선택, 모음, 찾아야할 값들

2. 목표: 구성에 할당된 점수를 최대화, 최소화하는 것

 

- 그리디 선택 속성: 그 상황에서 가장 최적해를 선택하는 것

 

## 예제1. 잔돈 거스르기

1. 구성: 거슬러줘야 할 금액 정보, 종류별 동전들

2. 목표: 동전 수를 최소화

 

### 일반적 상황(그리디 선택 속성)

32원, 8원, 1원 -> 32원 이상의 금액은 32원 없이 만들 수 없음

 

### 반례

30원, 20원, 5원, 1원 -> 40원은 20+20이 해! (30원 사용안함)

 

## 예제2. 부분적 배낭 문제

가장 대표적인 문제인 냅색 문제의 변형문제.

Item의 일부도 사용가능

 

1. 구성: 

 

 

---

# 최소신장트리 알고리즘

모두 탐욕 알고리즘을 기반으로 작성됨

 

## 1. 프림 알골즘

대상: 단순 연결 무방향 가중그래프

 

1. 임의의 정점 s 선택

2. s로 부터 시작하여 정점들을 배낭에 넣음.

3. 배낭 안에서 MST T를 키워나감 (s는 T의 루트노드)

 

d(v) : 배낭 안의 정점과 배낭 밖의 정점을 견결하는 간선의 무게 (정점 v)

 

반복에서

- 배낭 밖의 정점들 중 최소 d(z)인 정점 z를 배낭에 넣음.

- z에 인접 정점(x)들 d(x)을 최신화

 

Alg PrimJarnikMST(G)

forEach v <- G.vertices
	d(v) <- ∞
    p(v) <- ∅ // 부모
s<- G의 정점
d(s) <- 0
Q <- d로 라벨링된 모든 정점을 포함하는 우선순위 큐
while(!Q.isEmpty)
	u<-Q.removeMin()
    forEach e<- G.incidentEdges(u)
    	z<-G.opposite(u,e)
        if((z ⋳ Q) & (w(u,z) < d(z)))
        	d(z) <- w(u,z)
            p(z) <- e
            Q.replaceKey(z, w(u,z))