최소 스패닝 트리
[알고리즘 소개]
정점들과 가중치가 존재하는 간선들이 존재할 때, 해당 간선들을 이용하여 최소 스패닝 트리를 얻을 수 있는 알고리즘.
[알고리즘 특징]
- 그리디
- 우선 순위 큐 사용
- 분리 집합 사용
[코딩 방법]
- 우선 순위 큐와 분리 집합용 배열 생성. 배열의 크기는 정점의 개수
- 최소 스패닝 트리의 가중치를 저장할 result, 반복문 종료조건을 위한 count 변수 생성
- 두 정점과 가중치를 저장할 간선 클래스(구조체) 생성
- <연산자 재정의 (compareTo 재정의) → 낮은 가중치 우선
- 모든 간선에 대한 정보를 클래스(구조체)에 담아 우선 순위 큐에 삽입
- 우선 순위 큐에서 간선에 대한 정보를 꺼내는 작업 반복
- 정점 u, v가 Union이 가능한지 확인
- 불가능 하다면 continue, 가능하다면 u, v를 Union하고 count를 1증가 후 result += w(가중치)
- count가 V(정점의 개수) - 1이 됐다면 반복을 종료
[시간 복잡도]
$O(eloge)$
[공부용 링크]
'정리 > 알고리즘' 카테고리의 다른 글
| [알고리즘] KMP (0) | 2023.02.05 |
|---|---|
| [알고리즘] 이분 탐색 (Binary Search) (0) | 2023.01.15 |
| [알고리즘] 뤼카의 정리 (Lucas' Theorem) (2) | 2021.03.27 |
| [알고리즘] 페르마의 소정리를 이용한 이항 계수 (2) | 2021.03.27 |
| [알고리즘] 파스칼의 삼각형 (Pascal's Triangle) (0) | 2021.03.26 |