[Algorithm] 크루스칼

[2d3k]

크루스칼 알고리즘에 대해 설명하시오

[2d3k]

크루스칼 알고리즘은 최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 알고리즘 중 하나입니다.

최소 신장 트리는 그래프의 모든 정점을 포함하면서 사이클을 형성하지 않는 간선들로 구성된 트리를 말합니다. 간선의 가중치의 합이 최소가 되도록 구성됩니다.

크루스칼 알고리즘의 동작 과정은 다음과 같습니다.

• 간선들을 가중치의 오름차순으로 정렬합니다.
• 가중치가 가장 작은 간선부터 그래프에 추가합니다.
• 추가할 때 사이클을 형성하는지 검사합니다. 사이클을 형성하지 않으면 해당 간선을 트리에 추가합니다.
• 모든 정점이 포함될 때까지 2~3 단계를 반복합니다.

이 알고리즘은 그리디 알고리즘으로 분류됩니다. 즉, 각 단계에서 최적의 선택을 하는 방식으로 최종 결과를 도출합니다. 이 알고리즘의 시간 복잡도는 O(ElogE)입니다. (E는 간선의 개수)

[hyeonayou]

1. 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘'이라고 하는데, 대표적인 최소 신장 트리 알고리즘으로는 크루스칼 알고리즘이 있다. 크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다.

신장 트리란? 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.

최소 신장 트리란? 신장 트리의 조건을 만족하면서 최소 비용으로 만들 수 있는 신장 트리

크루스칼 알고리즘 동작과정

1.간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2.간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. ① 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다. ② 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다. (X) 3.모든 간선에 대하여 2번의 과정을 반복한다.