Spanning Tree(신장 트리)

그래프 내의 모든 정점을 포함하는 트리

• 모든 정점들이 연결되어 있어야 한다.
• 사이클이 없어야 한다.
• n개의 정점을 n-1개의 간선으로 연결해야 한다.
  

예시

회사 내의 모든 전화기를 가장 적은 수의 케이블을 사용하여 연결하고자 하는 경우!

---

MST(Minimum Spanning Tree - 최소신장트리)

간선의 가중치를 고려할 때 최소 비용인 신장트리

조건

• 간선의 가중치 합이 최소여야한다.
• n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
• 사이클이 포함되어서는 안된다.

---

MST 알고리즘

Kruskal Algorithm

크루스칼 알고리즘은 가중치를 기준으로 간선을 정렬한 후에 MST가 될 때까지 간선을 하나씩 선택 또는 삭제해 나가는 방식이다.

간선 선택에 의한 탐색 방법

1. 간선의 가중치를 오름차순으로 정렬한다.
2. 낮은 가중치의 간선부터 선택한다.
   2-1. 만약 간선을 선택했을 때 사이클이 생기면 건너뛴다.

이 행동을 간선의 수가 정점의 수 + 1이 될 때까지 한다.

간선 제거에 의한 탐색 방법

1. 간선의 가중치를 내림차순으로 정렬한다.
2. 가장 큰 가중치의 간선부터 제거한다.
   2-1. 간선을 제거했을 때 어떤 경로로도 방문할 수 없는 정점이 생기면 건너뛴다.

이 행동을 간선의 수가 정점의 수+1이 될때까지 한다.

Prim Algorithm

프림 알고리즘은 특정 정점을 시작으로 MST가 될 때까지 트리를 확장해나가는 방식이다. 시작점은 어떤 정점이든 상관없다.
그리디 알고리즘으로 분류된다.

동작 과정

1. 하나의 정점을 선택한다.
2. 시작점에서 연결된 가중치 중 제일 작은 가중치를 가지고 있는 간선을 선택한다.
3. 연결된 정점과 기존 정점 중에서 연결 될 수 있는 간선 중 가장 작은 가중치를 가지고 있는 간선을 택한다.
   3-1. 가장작은 간선을 선택했을 때 사이클이 생기면 그 다음으로 작은 간선을 선택한다.

이 행동을 모든 정점이 연결될 때 까지 반복한다.