Hyunebee
최소 신장 트리(MST) 본문
그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법
크루스칼, 프림 2가지가 존재
크루스칼
간선 중 최소 값을 가진 간선부터 연결
사이클 발생 시 다른 간선 선택
주로 간선 수가 적으면 사용
O(ElogE)
프림
임의의 노드에서 시작
연결된 노드의 간선 중 낮은 가중치를 갖는 간선을 선택
간선의 개수가 많을 때 크루스칼 보다 유리하다.
O(ElogV)
'zerebase > 자료구조' 카테고리의 다른 글
| DP(동적 계획법) (0) | 2022.05.31 |
|---|---|
| 그리디 알고리즘 (0) | 2022.05.17 |
| 투포인터 (0) | 2022.05.16 |
| 정렬 알고리즘(버블, 선택, 삽입) (0) | 2022.05.12 |
| 우선 순위 큐 (0) | 2022.05.10 |
'zerebase/자료구조' Related Articles
more
