알고리즘(Algorithm)
최소 신장 트리(MST) - Kruskal 알고리즘 / Prim 알고리즘
꼬꼬랑내
2021. 9. 21. 12:59
신장 트리
그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
N개의 정점으로 이루어진 무향 그래프에서 N개의 정점과 N-1개의 간선으로 이루어진 트리
최소 신장 트리
무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장트리
특징
- 간선의 가중치의 합이 최소여야 한다.
- n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
- 사이클이 포함되어서는 안된다.
Prim 알고리즘
정점 중심
1. 임의의 한 정점을 선택
2. 선택한 정점과 인접한 정점 중에 최소 비용 간선이 존재하는 정점을 선택
3. n-1번 반복
Kruskal 알고리즘
간선 중심
1. 모든 간선을 가중치에 따라 오름차순 정렬
2. 가중치가 낮은 간선부터 선택하여 트리를 증가시킴 - 사이클이 발생하면 그 다음 간선을 선택
3. n-1번 반복
출처
https://pyrite-emu-d92.notion.site/c1824e4ad68c46948dc235f160f68392