Data Structure : 최소비용신장트리 - Kruskal's Algorithm

Data Structure : 최소비용신장트리 - Kruskal's Algorithm

Kruskal의 알고리즘은 Greedy Strategy로, 각 스텝마다 가능한 최선의 선택지를 고르는 것을 반복하여 결과를 얻어낸다.

 

Kruskal 알고리즘은 주어진 가중치 그래프에서 최소비용인 신장트리를 뽑아내는 것을 목표로 한다.

( 신장트리 : vertex를 모두 연결하면서 edge의 개수가 n-1개인 트리 )

규칙

1. 한 번에 하나씩 간선을 추가한다.
2. 추가되는 간선의 순서는 비용의 크기를 기준으로 선택한다.
3. 간선을 추가했을때 사이클이 형성되지 않는 간선만 추가 가능하다.
   • 사이클이 형성되는가? 에 대해서는 'Union-Find'를 이용한다.
4. 간선의 개수가 n-1인 경우 ( Spanning Tree 만족 ) 또는 남은 Edge가 없는 경우 ( Spanning Tree X ) 종료한다.

Kruskal 알고리즘

T = {  };        // T는 선택된 edge의 집합, E는 전체 edge의 집합, N은 Tree의 Vertex의 개수

while ( T 가 n-1개의 edges를 가지지 못하면 && E가 비어있지 않으면) {

        E에서 가장 비용이 작은 edge를 고름

        해당 edge는 E 집합에서 삭제

        만약 선택한 edge가 T에 추가되었을 때 사이클을 만들지 않으면 T에 추가 // Union-Find

}
if(T가 n-1의 개수가 안되면) {
      T는 Spanning Tree가 아니다
}

Kruskal 알고리즘의 동작방식

왼쪽의 Graph가 원본 그래프이고, 그래프를 토대로 최소비용신장트리를 구하고자 한다.

최소비용인 edge를 추가하며 Tree를 채워가다가 (3, 6) edge가 Cycle을 만들게되므로 다음 비용의 edge를 찾는다.

(4, 6) edge도 같은 이유로 추가될 수 없다.

(0, 1) 노드의 경우 이미 Spanning Tree의 조건인 edge의 개수 = vertex개수 - 1 을 만족했으므로 추가될 수 없다.

알고리즘 실행 결과로 붉은 색 edge들로 구성된 Spanning Tree를 얻을 수 있다.

Kruskal 알고리즘의 시간복잡도

Edge들을 Cost에 대해 작은 값 부터 정렬하는데 걸리는 시간 O( n log n )

사이클이 형성되었는지 탐색하는 알고리즘 Union - Find 에 걸리는 시간 O( log n ) 이 n번 반복되므로 O ( n log n )

따라서 Kruskal 알고리즘의 시간복잡도는 O ( n log n ) 에 해당한다.