정의
•
크루스칼 알고리즘이란 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위한 알고리즘이다.
•
그래프 내의 모든 정점을 포함하고 사이클이 없을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을때 사용한다.
•
즉 최소 신장 트리를 구하기 위한 알고리즘이다.
신장 트리와 최소 신장 트리
•
신장 트리는 다음과 같이 정의된다.
◦
그래프에서 모든 정점을 포함하고, 정점 간 서로 연결이 되며 싸이클이 존재하지 않는 그래프
•
따라서 신장 트리는 정점의 갯수가 n이라면 이를 연결하는 간선의 갯수는 n-1개가 된다.
•
이런 신장 트리들 중에서 가중치의 합이 최소가 되는 신장 트리를 최소 신장 트리라고 한다.
구현
•
크루스칼 알고리즘은 그리디 알고리즘의 일종으로 정렬을 사용한다.
◦
그래프의 간선을 가중치를 기준으로 오름차순으로 정렬한다.
◦
사이클을 형성하는지 검사한 후, 연결에 추가한다.
▪
부모가 같다면 이는 싸이클을 형성하게 된다. 이미 연결되어있기 때문이답..!
