신장트리란?
- spaning tree 라고하며
- 모든노드가 모두 서로 연결되어있으며,
- 사이클이 존재하지않는것(트리의속성)
최소신장트리란?
- minimum Spanning Tree
- 신장트리의 연결된 간선의 합이 최소인 신장트리
최소신장트리 알고리즘
- 크루스칼 알고리즘
- 프림 알고리즘
크루스칼알고리즘
탐욕알고리즘 기반
모든노드를 간선을 기준으로 정렬한후 간선이 낮은것부터 연결한다.
'TechKnowledge > 알고리즘' 카테고리의 다른 글
| 프로그래머스 lv2 멀리뛰기 자바(Java) 동적계획법/ 피보나치수열 (2) | 2023.01.31 |
|---|---|
| 백준 2775: 부녀회장이 될테야 Java(자바) 동적계획법을 이용한 풀이 (0) | 2023.01.10 |
| 항해 알고리즘 4일차 (0) | 2022.05.17 |
| 항해 알고리즘 3일차 (0) | 2022.05.16 |
| 항해 알고리즘 2일차 (0) | 2022.05.14 |