📚 목차
요약
1. 최소 신장 트리(Minimum Spanning Tree)
1. 최소 신장 트리
- 그래프의
모든 노드를 연결할 때 사용된 엣지들의 가중치의 합을 최소로 하는 트리
2. 최소 신장 트리의 특징
- 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 유니온 파인드로 사이클의 유무를 확인한다.
- 즉, 유니온 파인트를 통해 연결하려는 두 노드가 동일하면 연결하지 않는다.
- N개의 노드가 있으면 최소 신장 트리를 구성하는 엣지의 개수는 N - 1개다.
3. 최소 신장 트리의 핵심 이론
- 엣지 기준 리스트 (엣지, 연결노드, 가중치) 와 유니온 파인드 배열을 만든다.
엣지 기준 리스트
| 에지 |
1 |
2 |
3 |
4 |
5 |
6 |
| 노드 1 |
1 |
2 |
1 |
3 |
2 |
4 |
| 노드 2 |
2 |
5 |
3 |
4 |
4 |
5 |
| 가중치 |
8 |
5 |
3 |
13 |
4 |
2 |
유니온 파인드 배열
- 그래프 데이터 가중치 기준으로 정렬하기