[그래프 알고리즘]kruskal 알고리즘(MST)

MST Minimum Spanning Tree

MST란 한 무향 그래프에서 특정 엣지들의 집합으로, 모든 노드들을 연결하면서, 가중치의 합이 제일 작은 엣지들의 집합입니다.

MST는 트리이므로 엣지들의 개수는 노드의 개수에서 1을 뺀 수입니다.

크러스칼 알고리즘

크러스칼 알고리즘은 그래프의 엣지를 가중치 순으로 정렬한 뒤, 작은 가중치의 엣지를 MST에 포함해갑니다.

MST는 사이클이 있어서는 안되므로, 추가하는 엣지가 사이클을 만든다면 포함하지 않습니다.

MST가 모든 노드를 연결할 때까지 반복합니다.

Union and Find

한 엣지를 추가하면 사이클을 이루는지 확인하기 위해 union and find를 이용합니다.

엣지를 추가할때마다 두 노드를 같은 그룹으로 묶습니다. 만약 추가할 엣지의 두 노드가 이미 같은 그룹이라면 제외합니다.

구현