[이산수학] 최소 신장트리와 프림/크루스칼 알고리즘

<< 이산수학 8주차 >>

트리는 그래프의 유형이다.
1. 무방향
2. 모든 정점 연결
3. 비순환

루트 트리(Rooted Tree, top)
: 지정된 한 개의 정점을 갖는다.
뿌리 보다는 top이라고 생각하자. (->정상에 있는 정점)

루트 트리와 관련된 용어 // 정점
- 부모 정점 : 바로 위 정점
- 조상 정점 : 위에 있는 정점 모두
- 자식 정점 : 바로 아래 정점
- 후손 정점 : 아래 있는 정점 모두
- 형제 정점 : 같은 부모
- 단말 정점 또는 잎 : 터미널 vertices, 마지막 노드
- 비단말 또는 내부 정점 : 단말 정점을 제외한 것
- 부 트리

** 만약 단말 정점인데 부트리를 구하라? >> 본인 자신 정점뿐

m-가지 루트 트리
: 자식이 최대 m개(m=2이면 이진트리)
  포화 m-가지 트리에는 각각 m개 자식이 있다.

순서화된 루트 트리
정점들이 순서 규칙에 맞게 위치함
- 왼쪽(작은 값, 먼저 나옴) / 오른쪽(큰 값, 뒤에 나옴)

일반 루트 트리(General Tree)
>> 제약이 없음, 폴더/파일 구조


① 이진 탐색 트리
: 순서화된 트리이다.
 문자열을 다룰 때에는 사전식 순서를 갖는다.
 문자열을 비교해서 앞쪽이면 왼쪽, 뒤쪽이면 오른쪽에 위치함

② 허프만 코드
: ASCII 코드에서 인코딩과 디코딩 예 (고정 길이 vs 가변 비트)
 A -> (100 0001)
 65(100 0001) -> A //코드에 의미를 부여함

허프만 코드 예시

허프만은 빈도수를 생각하여 많이 나오는 것들은 짧게 배정, 적게 나오는 것은 길게 배정
"트리로 나타내보자"
큰쪽이 왼쪽(1) / 작은 쪽이 오른쪽(0)

허프만 코드 >> 압축 파일 만들 때

③ 게임 트리
: 님(nim) 게임 >> 성냥개비 움직이기 게임
맨 마지막에 치우는 사람이 짐. 

: min & max 전략 >> 손해는 최소/피해는 최대
 갑의 입장에서의 승리 전략? 

④ 쿼드 트리(Quad Tree)
: 4분할 

-----------------------------------------
 

★★트리 방문★★
>> 트리가 갖는 재귀적인 성질 이해

1. pre-order : root -> left -> right
2. in-order : left -> root -> right
3. post-order : left -> right -> root

일반 트리로 확장
맨 왼쪽만 left, 그 외 것들은 right

(트리 탐방의 활용 : 수식 다루기)
- infix(중위), prefix(전위), postfix(후위)
- 후위 연산이 컴퓨터 연산에 편함 >> 스택


신장 트리(Spanning Tree)
: 원본 그래프에서 정점을 모두 가지고 있지만 순환이 없는 트리

 >> BFS : 인접된걸(레벨로)
 >> DFS : 깊이로(+backtracking)

DFS+Backtracking : Coloring
DFS+Backtracking : Four-Queens Problem

최소 신장 트리
: 가중치 그래프에서 가중치 합이 최소인 신장 트리

★프림 알고리즘★
Prim (G) :
T=최소비용 간선
for  i=1  to  n-2
e = T + 인접한 것중에서 가장 작은 가중치를 갖는 간선(+순환 x)
T = e 추가

**프림의 알고리즘에서는 가장 적은 비용을 시작으로 붙여나갔는데,
 시작점을 주는 곳들도 많다. (미니멀 스패닝 트리에서 루트를 지정해줌)

★크루스 칼 알고리즘★
Krustkal (G) :
T = 빈 그래프
for  i=1  to  n-1
e = T + 가장 작은 가중치를 갖는 간선(+ 순환 x)
T = e 추가