신장 트리 (Spanning Tree)
- 그래프의 모든 정점을 연결하는 트리
- 트리: 일반적으로 계층구조의 자료구조를 생각하는데, 그래프 이론에서 사이클이 없는 무방향 그래프를 트리라고 한다.
- 그래프가 n개의 정점을 가질 때, 그래프의 최소 간선의 수는 n-1개이다.
- 하나의 그래프에서 여러개의 신장 트리가 존재할 수 있다.
최소 신장 트리 (Minimum Spanning Tree)
- Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리
- Spanning Tree와 마찬가지로 정점이 N개일 때, N-1개의 간선으로 연결된다.
- Spanning Tree와 마찬가지로 사이클이 없다.
- Spanning Tree와 마찬가지로 MST의 해가 여러개 일 수 있다.
MST을 구현하는 알고리즘으로 Kruskal(크루스칼) 알고리즘과 Prim(프림) 알고리즘이 있다.
2022.01.16 - [Algorithm] - [Algorithm] Krsukal (크루스칼) 알고리즘
[Algorithm] Krsukal (크루스칼) 알고리즘
Kruskal (크루스칼) 알고리즘 그래프의 모든 정점을 최소 비용으로 연결하는, 즉, 최소 신장 트리를 구현하는 대표적인 Greedy(탐욕) 알고리즘이다. Greedy 알고리즘 그 순간에 가장 좋다고 생각되는
jino-dev-diary.tistory.com
2022.01.16 - [Algorithm] - [Algorithm] Prim(프림) 알고리즘
[Algorithm] Prim(프림) 알고리즘
Prim(프림) 알고리즘 그래프의 모든 정점을 최소 비용으로 연결하는, 즉, 최소 신장 트리를 구현하는 대표적인 Greedy(탐욕) 알고리즘이다. Greedy 알고리즘 그 순간에 가장 좋다고 생각되는 해를 선
jino-dev-diary.tistory.com
'Algorithm' 카테고리의 다른 글
| [Algorithm] Prim(프림) 알고리즘 (0) | 2022.01.16 |
|---|---|
| [Algorithm] Krsukal (크루스칼) 알고리즘 (0) | 2022.01.16 |
| [Algorithm] BFS (Breath-First-Search, 너비 우선 탐색) (0) | 2022.01.08 |
| [Algorithm] DFS (Depth-First-Search, 깊이 우선 탐색) (0) | 2022.01.08 |
| [Algorithm] 정렬 - Heap Sort (힙 정렬) (0) | 2021.09.29 |