알고리즘 : MST (크루스칼, 프림)

* MST(Minimum Spanning Tree)

: 최소 신장 트리

무방향 그래프의 간선들에 가중치가 주어진 경우,

여러 신장 트리중에 간선들의 가중치 합이 최소인 신장트리

-> 크루스칼, 프림으로 구할 수 있음.

 

* 신장트리

: 무방향 그래프 G(V,E)에서 E에 속한 간선들로,

사이클을 포함하지 않으면서 모든 정점 V를 연결한 부분 그래프

 

- 특징 : n개의 정점 갖는 그래프에서 신장트리에 속하는 간선 수는 n-1개(n은 정점), 사이클을 이루지 않음.

 

 

1) 크루스칼(Kruscal)

: greedy 하게(결정의 순간마다 최선의 결정을 반복하여 최종적인 해답에 도달) 모든 정점을 최소 비용으로 연결

 

- 특징 : 간선을 가중치 기준 오름차순 정렬하고, 이 간선들을 순서대로 모든 정점들이 연결될 때까지 반복

 

- union-find 알고리즘 사용해서 구현 가능, 시간 복잡도 O(1) 이므로, 간선을 정렬하는 로직이 전체 시간 복잡도를 좌우.

퀵정렬이라고 예시를 들면, O(ElogE) (E: 간선 개수)

 

 

2) 프림(Prim)

: 임의의 정점을 시작점으로 잡고, 아직 연결되지 않은 정점들에 대해 최소 가중치를 갖는 정점을 연결해나가며 트리를 단계적으로 확장

-> 정점 선택 기반 동작, 트리 집합 단계적 확장

 

- 새로운 정점 연결 할 때마다, 새로운 정점에서 갈 수 있는 아직 연결되지 않은 정점들에 대한 간선 정보가 추가로 필요.

 

- Priority Queue 이용한 최소힙으로 구현 가능, 다익스트라와 구현 방식 유사

최소힙을 사용하면 O(ElogV) (E: 간선 개수, V:정점 개수) / 최소 힙X O(V²) / 피보나치 힙 O(E + VlogV)