신장 트리 (Spanning Tree)
1. 그래프의 모든 정점이 간선으로 연결되어 있다.
2. 그래프 안에 사이클이 포함되어 있지 않다.
최소 신장 트리(Minimum Spanning Tree)
말그대로 최소 비용으로 만들어진 신장 트리. 가중치의 합이 가장 작은 신장 트리
Prim, Kruskal 알고리즘은 최소 신장 트리를 구하는 방법이다. 두 알고리즘 모두 Greedy Method를 기반으로 한다.
'알고리즘' 카테고리의 다른 글
| #알고리즘_조합과 순열(조합, 중복조합, 순열, 중복순열) - Java (0) | 2020.01.09 |
|---|---|
| #알고리즘_선형 탐색/이진 탐색 - Java (0) | 2020.01.08 |
| #알고리즘_프림(Prim Algorithm) - Java (0) | 2020.01.08 |
| #알고리즘_크루스칼(Kruskal Algorithm) - Java (0) | 2020.01.07 |
| #알고리즘_다익스트라(Dijkstra Algorithm) - Java (0) | 2020.01.07 |