최소 신장 트리 (MST : Minimum Spanning Tree)
그래프 상의 모든 노드들을 최소 비용으로 연결하는 방식의 알고리즘이다.
① 크루스칼 (Kruskal)
간선 중 최소 값을 가진 간선부터 연결하는 방식이다.
주로 간선 수가 적을 때 사용하며, 연결 도중에 사이클이 발생하면 다른 간선을 선택한다.
알고리즘 복잡도 : O (ElogE)
- 사이클 발생 체크
Union - Find 배열 사용
(Union - Find : 노드 수에 맞춰서 자기 자신의 최종 부모노드가 무엇인지 나타내는 배열을 만들고 부모 노드가 2개 초과 할 경우 사이클 발생)
② 프림 (Prim)
임의의 노드에서 시작하는 방식이다.
연결된 노드들의 간선 중 낮은 가중치를 갖는 간선을 선택하며, 간선의 개수가 많을 때는 크루스칼 보다 유리하다.
알고리즘 복잡도 : O(우선순위 큐 사용시 : ElogV , 정렬되지 않은 상태에서 진행 시 : V²)
visited 배열 같이 사용