[알고리즘] MCST - Kruskal's Algorithm (크루스칼 알고리즘)

Spanning Tree (신장 트리)

 

• Graph의 모든 Vertex를 포함하는 Sub Graph이자 Tree
• 모든 정점들이 연결되어 있어야 한다.
• 사이클이 없어야 한다. (트리니까)
• Edge의 개수는 N-1개이다. (N: Node의 수)

MCST (최소 비용 신장 트리)

• Minimun Cost Spanning Tree
• Graph의 신장 트리 중 Edge의 가중치 합이 최소인 신장 트리

MCST - Kruskal's Algorithm

1. Edge들을 가중치 기준으로 오름차순 정렬 (가중치 작은 거 -> 큰 거)

2. 가중치가 작은 Edge들부터 시작하여 다음을 반복

   1) 선택된 Edge의 양 끝 Node들이 속한 집합을 확인한다. (Find)

   2) 같은 집합에 속하지 않다면 : 두 Node가 속한 집합을 합친다. (Union)

       같은 집합에 속한다면       : 넘어간다.

   3) 그 Edge를 MCST의 Edge로 취급한다.