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

 

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

---

신장 트리 : 모든 정점이 연결된 그래프, 사이클이 존재하지 않아야 한다.

• n개의 점을 (n-1) 개의 간선으로 연결한다.

최소 신장 트리 : 신장 트리 중 간선 가중치의 합이 가장 작은 신장 트리를 의미한다.

 

 

Prim(프림) 알고리즘

---

시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법이다.

 

수행 과정

1. 임의의 정점을 시작 지점으로 선택
2. 연결된 모든 간선의 가중치를 비교
3. 가장 작은 무게의 간선 선택(사이클이 만들어지지 않도록)
4. 모든 정점이 연결될 때까지 2~3번 과정 반복

 

시간복잡도

V : 정점의 개수

E : 간선의 개수

1. 우선순위 큐로 구현
   • 우선순위 큐 생성 작업 : O(logV) * O(E) = O(ElogV)
     • 각 노드에서 인접 간선을 찾는 작업 : O(V의 차수) = O(2E) = O(E)
     • 힙에 삽입 : O(logV)
   • 총 탐색 작업 : O(VlogV)
     • 모든 노드 탐색 : O(V)
     • 노드에서 최소 간선 탐색 : O(logV)
   • 총 시간복잡도 : O(ElogV + VlogV) = O(ElogV)
     • 보통 E가 V보다 크기 때문에 O(ElogV) 라고 할 수 있다.
2. 배열로 구현 : O(V^2)
3. 피보나치 힙으로 구현 : O(E+VlogV)

 

Kruskal(크루스칼) 알고리즘

---

탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

 

수행 과정

1. 모든 간선을 무게 순으로 정렬
2. 가장 작은 가중치의 간선 선택(사이클이 만들어지지 않도록)
3. 모든 정점이 연결될 때까지 2번째 과정 반복

 

시간복잡도

• 간선 정렬 : O(ElogE) E : 간선의 개수
• find 작업 : 정점이 속한 집합을 반환한다. - O(1)
• union 작업 : 두 집합을 합친다 - O(1)
• 총 시간복잡도 : O(ElogE)