크루스칼 알고리즘은 대표적인 최소 신장 트리를 찾는 알고리즘이다.

신장트리

그래스에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분그래프

모든 노드가 포함되어 서로 연결되며 사이클이 존재하지 않는 것은 트리라고도 할 수 있다.

신장트리의 간선 수는 (노드수 -1)개이다. (트리의 기본적 특성)

https://devlog-wjdrbs96.tistory.com/97

위 그림의 (a)처럼 사이클이 존재하는 경우는 신장트리라고 할 수 없다.

최소신장트리 문제

최소한의 비용으로 구성되는 신장트리를 찾는 문제이다.

ex) N개의 도시가 존재할 때

• 두 도시 사이 도로를 놓아 전체 도시가 서로 연결되도록 도로를 설치하는 경우
• 모든 도시를 최소한의 비용으로 방문하는 경우

크루스칼 알고리즘

• 최소신장트리 알고리즘
• 그리디 알고리즘
• 동작과정
  1. 간선 데이터를 비용에 따라 오름차순 정렬 ⇒ 비용이 적은 간선부터 확인
  2. 간선 하나씩 확인하면서 현재의 간선이 사이클을 발생시키는지 확인
     • 사이클 발생 x인 경우 : 최소 신장 트리에 포함
     • 사이클 발생 시 : 최소 신장 트리에 포함 x
  3. 모든 간선에 대해 2번 반복

예시

(1)오름차순 정렬