신장 트리(Spanning Tree)
- 하나의 그래프가 있을 때, 모든 노드들 간에 서로 연결은 되어 있되 사이클을 발생시키지 않는 부분 그래프를 의미한다.
최소 신장 트리(MST)
- 신장 트리들 중에서 최소의 간선 비용으로 만들 수 있는 신장 트리를 최소 신장 트리라고 한다.
크루스칼 알고리즘
- MST를 찾는 알고리즘 중 하나
- 가장 적은 비용으로 모든 노드를 연결하게 함 -> 그리디 알고리즘으로 분류되기도 한다.
크루스칼 알고리즘 동작 과정
1. 주어진 모든 간선 정보에 대해 간선 비용이 낮은 순서로 정렬
2. 정렬된 간선 정보를 하나씩 확인하면서, 현재의 간선이 사이클을 발생시키는지 확인
3. 사이클이 발생하지 않으면, MST에 포함시키고 그렇지 않으면 MST에 추가하지 않음
4. 1~3의 과정을 모든 간선 정보에 대해 반복시킴
위 과정을 살펴보면, 사이클을 발생시키는지 여부에 따라 MST에 포함시킬지 아닐지를 결정한다.
사이클을 발생시키는지에 대한 여부는, 노드의 부모 노드가 같은지 아닌지로 판별한다.
노드의 부모 노드가 같으면 사이클이 발생한다.
