[알고리즘] 크루스칼 알고리즘

크루스칼은 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘으로 가장 적은 비용으로 모든 노드를 연결하기 위해 사용한다. 즉 노드를 연결해 모든 노드가 다 연결되게 할 때 제일 적은 비용을 사용하는 방법을 찾는것이다. 예를 들어 여러 개의 도시가 있을 때 각 도시를 도로를 이용해 연결할 때 최소한의 비용으로 하는 알고리즘

 

노드=정점=도시 -> 그래프에서 동그라미 부분

간선=거리=비용 -> 그래프에서 선에 해당하는 부분

 

최소비용신장트리의 간선숫자는 노드숫자 -1이다

위 그래프에서 노드는 7개, 간선은 10개, 최소비용신장트리의 간선 숫자는 6개이다

 

크루스칼 구현 과정

1. 모든 간선 정보를 오름차순으로 정렬

2. 비용이 적은 간선부터 사이클이 발생 안 한다면 차근차근 그래프에 포함. 사이클이 발생하면 안됨

3. 간선비용을 하나씩 더해줌

빨간색 선이 실제로는 추가하는 과정이다