IT&컴퓨터공학/자료구조&알고리즘
[알고리즘] 최소 신장 트리
yan_z
2021. 2. 14. 20:43
신장트리
- Spanning Tree 라고 불린다.
- original 그래프의 모든 노드가 연결되어 있으면서, 트리의 속성을 만족하는 그래프
- 신장트리의 조건
- 본래의 그래프의 모든 노드를 포함해야 한다.
- 모든 노드가 연결되어있어야 하지만
- 사이클이 존재하지 않아야 한다 ( 트리 이므로 )
최소 신장트리
- MST 라고 불린다.
- 가능한 신장트리 중에서 간선의 가중치 합이 최소인 신장트리
최소 신장트리를 찾는 알고리즘 2개
- 크루스칼 알고리즘
- 프림 알고리즘
크루스칼 알고리즘
- 모든 간선들의 가중치를 오름차 순으로 정렬
- 가중치가 가장 작은 간선을 선택
- 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다. ( 이때 사이클이 만들어지면 안된다 !)
- 이 과정을 반복
프림 알고리즘
1. 임의의 간선을 선택한다.
2. 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택한다. ( 이때 이미 선택된 정점은 선택하지 않는다 )
3. 모든 정점이 선택될 때까지 반복한다.