[자료구조] Graph - Minimum Spanning Tree, Kruskal, Prim

자료구조 07 - 3 / Graph

---

정의 

MST: Minimum Spanning Tree

 

- 사용된 간선들의 가중치 합이 최소인 트리, 모든 정점을 방문하는데 사용되는 최소 비용 경로

Spanning Tree (신장트리) : 순환이 없는 최소 연결 그래프 (간선의 수가 최소) n개 정점 -> n-1개 간선

 

Kruskal Algorithm

-  Greedy Method(탐욕적 방법) 을 이용해서 모든 정점을 최소 비용으로 연결, 결정 순간마다 가장 최적의 방법으로 진행

시간 복잡도 O(elog₂e) <- 간선 정렬 시간 / 간선이 적은 Sparse Graph에 적합

 

알고리즘 :

1. 그래프 간선들 가중치 오름차순 정렬

2. 간선 정렬 순으로 사이클 형성하지 않는 지 확인 -> Union-Find 알고리즘으로 사이클 존재 확인

3. 간선 선택 MST에 destination 정점 넣기

 

 

Prim Algorithm

- 시작 정점부터 신장트리 집합을 단계적으로 방문하며 확장, 연결된 간선 중 낮은 가중치를 먼저 선택

시간 복잡도 O(n²) <- 정점의 수 n번 반복 * 내부 반복 n번 / 간선이 많은 Dense Grpah에 적합

 

알고리즘 :

1. 현재 정점이 가진 간선 리스트 중 최소 가중치 가진 간선 pop -> 간선의 최소 값 pop 할 우선순위 큐

2. 해당 간선의 destination 정점이 MST에

   - 있으면 다른 간선 pop

   - 아니면 해당 정점으로 이동

3. 도착한 정점의 간선 리스트를 만듬

 

 

활용

통신 네트워크

 

구현

 

Kruskal Algorithm

 

Prim Algorithm

 

추가적으로 생각해볼 내용

면접 예상질문

Q: 

A:

 

Reference : raywenderlich.com github Kruskal1 Kruskal2 Prim1 Prim2