[알고리즘] 최소 신장 트리 개념

 

책을 보면서 그리디 알고리즘으로 최적해가 보장되는 예로

최소 신장 트리가 있었다!

당연히 기억 안나니까 한번 공부해 볼까?!!

---

 

최소 신장 트리

" 간선들이 가중치를 갖는 그래프에서 가중치의 합이 가장 작은 트리를 말한다. "

 

최소 신장 트리를 찾는 알고리즘을 공부해보려 한다.

---

 

1. 프림 알고리즘 

: 시작점을 기준으로 모든 정점을 포함할 때까지 인접한 정점에서 가중치가 가장 작은 간선을 선택하여 하나씩 확장해 나간다. 

          프림 알고리즘 v1 .made 부찌여

 

 

[순서]

1. Start 에서 바라보면 8,9,11 중에서 가장 가중치가 낮은 간선을 택한다.

 

2. 연결되어 있는 간선들 중에 가중치가 가장 낮은 9를 선택한다.

 

3. 연결된 간선(1,10,11,12,13) 중 가장 낮은 5를 선택한다. 

 

4. 연결된 간선(11,12,13) 중 가장 낮은 11을 선택한다.

 

5. 같은 방식으로 반복하면 짜짠!

 

[해석]

: 동그라미를 집합 S라고 했을때 집합이 채워지면 주위 간선들은 중요치 않다는 것을 볼 수 있다.  >> 노드중심

  (최소 간선이 채워진 것이므로!!)

 

---

 

2. 크루스칼 알고리즘

: 사이클을 만들지 않는 범위에서 간선을 하나씩 확장해 나간다. 

 

[순서]

1. 가장 간선의 가중치가 낮은 5부터 간선을 연결해준다. 

 

2. 그 다음으로 가장 가중치가 낮은 7을 선택한다.

 

3. 가중치가 낮은 간선을 순서대로 선택한다.

 

4. 이제 가장 낮은 간선은 10이 되는데 10을 연결하면 사이클이 생기므로 10 간선은 연결하지 않는다.

5. 다시 가중치가 낮은 순서대로 사이클이 생기지 않게 간선을 선택한다.

 

6. 사이클이 생기지 않게 간선을 연결하면 짜잔!

 

[해석]

: 가중치가 낮은 간선부터 순서대로 선택한다. 단, 사이클이 생기지 않도록 주의해야한다.  >> 간선중심

 

---

 

최소 신장트리의 개념을 알아보았다. 한번 배웠던 것이라서 그런지 개념을 익히는데 어렵지 않았다!!

알고리즘 재밌는거 같당ㅎ

---