[SW사관학교 정글/19일차 TIL] 크루스칼 알고리즘

크루스칼 알고리즘

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위한 알고리즘

크루스칼 알고리즘은 최소 비용 신장 트리(Minimum Spanning Tree)를 만들기 위한 대표적인 알고리즘이다.

예를 들어 이러한 그래프가 있다고 가정해보자

이 트리를 가장 적은 비용으로 모든 노드를 연결해보자.

그러기 위해서는 모든 정점이 포함되어 있으면서, 모든 노드는 적어도 하나의 간선으로 연결되어있어야 한다.

또한 연결관계에서 사이클을 형성하지 않아야 한다.

위의 그래프에서 간선을 제거하여 최소 비용 신장 트리로 만든 결과는 다음과 같다.

주의할 점은 사이클을 형성하면 안된다는 점이다!

이를 위해 사이클 테이블을 만들어 사이클이 되었는지 아닌지를 검증해주어야 한다.

이것을 구현하기 위해서는 다음과 같은 순서를 따르면 된다.

1. 가중치가 작은것부터 그래프에 포함시기기 위해서 간선의 가중치를 기준으로 오름차순 정렬한다.
2. 사이클을 형성하면 안되기 때문에 사이클 테이블을 만들어서 사용된 노드(정점)를 확인한다.
3. 순서에 맞게 그래프에 포함시킨다.
4. 사이클을 형성하는 경우에는 간선을 포함하지 않는다.

여기에서 사이클이라는 것은 말 그대로 그래프가 거로 연결되어 사이클을 형성하는 경우이다.

최소 비용 신장 트리에서는 사이클이 발생하면 안된다.

그리고 크루스칼 알고리즘은 당장 선택할 수 있는 선택지중에 가장 큰(작은) 선택을 하기때문에 그리디 알고리즘의 일종이라고 할 수 있다.

공부하면서 본 자료들

18. 크루스칼 알고리즘(Kruskal Algorithm)

19강 - 크루스칼 알고리즘(Kruskal Algorithm) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #19 ]