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

 

크루스칼 알고리즘이란?

 

크루스칼 알고리즘은 최소 신장트리(MST)를 찾는 알고리즘으로, 주어진 그래프에서 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되도록 간선을 선택합니다.

 

 

기본 개념

 

크루스칼 알고리즘은 간선 중심으로 작동하며, 가장 가중치가 작은 간선부터 차례대로 선택해 나간다.

선택한 간선이 현재까지 선택된 간선들과 사이클을 형성하지 않으면 그 간선을 MST에 포함시킵니다.

이를 위해 Union_Find(합집합 찾기) 자료구조를 사용하여 사이클 여부를 효과적으로 관리합니다.

 

유형

 

주로 가중치가 주어진 무방향 그래프에서 MST를 찾는 데 사용되며, 그 유형은 문제의 특성에 따라 다양하게 적용 될 수 있습니다.

 

• 단순 그래프에서 MST 찾기
• 가중치가 음수인 경우에도 적용 가능
• 특정 조건을 만족하는 간선들만 사용한 MST 찾기 

 

크루스칼 알고리즘을 적용해야 할 힌트들

 

• 간선 리스트가 주어지고, 각 간선에 가중치가 주어짐: 크루스칼 알고리즘은 간선의 가중치에 따라 선택하는 방식이므로, 간선의 목록이 주어지고 각 간선의 가중치를 비교하는 형태의 문제가 크루스칼을 적용할 수 있는 좋은 후보다.

 

• 사이클을 피하면서 연결을 해야 하는 문제: 크루스칼 알고리즘은 사이클을 피하면서 간선을 선택하는 방식이므로, 그래프가 연결되어야 하면서 사이클을 방지해야 하는 문제에서 유용함.

 

• 간선의 개수가 적고, 간선을 정렬할 수 있는 경우: 크루스칼 알고리즘은 간선들을 오름차순으로 정렬한 후, 차례대로 처리하므로 간선이 많지 않거나 정렬이 중요한 경우 사용됩니다.

 

크루스칼 알고리즘을 적용할 때의 전략

 

 

• 간선 리스트를 가중치 순으로 정렬한 후, 가장 작은 가중치의 간선부터 하나씩 선택합니다.
• 각 간선이 추가될 때마다 Union-Find 자료구조로 그 간선이 사이클을 만들지 않는지 확인합니다.
• 사이클을 만들지 않으면 그 간선을 MST에 추가하고, 모든 정점이 연결될 때까지 이 과정을 반복합니다.

크루스칼을 적용하기 좋은 문제 예시

 

• 도로 건설 문제: 여러 도시를 연결하는 도로의 비용이 주어졌을 때, 최소 비용으로 모든 도시를 연결하는 문제.
• 네트워크 연결 문제: 여러 컴퓨터를 연결하는데 최소 비용이 드는 네트워크를 구성하는 문제.