[알고리즘] 최소 신장 트리 ( Kruskal ) - JavaScript

최소 신장 트리? 

신장 트리란 그래프 내에 모든 정점을 포함하는 최소 연결 그래프이다.

최소 신장 트리가 되려면 아래 조건을 만족해야한다. 

 - 최소한의 간선으로 모든 정점이 연결되어야 한다. 

 - 모든 신장 트리 중 가중치의 값이 최소여야 한다. 

 - Cycle이 발생해서는 안된다. 

 

최소 신장 트리를 구현하기 위한 대표적인 알고리즘이 크루스칼 알고리즘이다. 

 

크루스칼 알고리즘?

그리디 개념을 이용해서 구현할 수 있다. 

 

모든 그래프를 부분 집합으로 분리하고 가중치가 낮은 간선을 선택해 연결한다. 

이때 Cycle이 발생하지 않도록 주의한다. 

=> Cycle을 판단하기 위해서 Union-Find 알고리즘을 이용한다. 

 

Union-Find 알고리즘?

공통 원소가 없는 두 집합을 구하기 위한 알고리즘이다. 

서로 다른 두 집합을 병합하는 Union과 어떤 집합에 속하는지 판단하는 Find를 나타낸다. 

 

일반적으로 트리 구조로 구성하고 편의상 재귀로 구현하는 경우가 많다.