[Algorithm] Kruskal Algorithm

개요

MST (Minimum Spanning Tree)를 구하는 알고리즘

what's MST?

모든 노드(Vertex)를 최소 비용으로 최소 간선(Edge)을 사용해 연결한 트리 (no cycle)
* MST의 Edge수는 Number Of Vertex - 1 이다.

Where to use MST?

• Network Design
• Approximation algorithms (ex. traveling salesperson problem)

 

When to use Kruskal

Get MST of undirected graph by Greedy algorithm

 

Algorithm

(1) Sort all edges in ordering by weight (ascending) => 최소 비용 간선 오름차순

(2) Pick the smallest edge and check the cycle using Union-Find

(3) if cycle exists -> discard it. 
    not exist -> Union it

(4) Repeat step (2) & (3) until V-1 edges in the spanning tree

 

 

 

Time Complexity

(1) Sort all edge 

O (E log V)

(2) check cycle using Union-Find

find : O(log n)

Union: O(1)

 

∴ O (E log V)