[알고리즘] 크루스칼(Kruskal) 알고리즘

프로그래머스 섬 연결하기 문제를 풀다가 알게된 알고리즘이다.
섬 연결하기 문제

크루스칼 알고리즘이란?

탐욕 알고리즘을 이용하여 모든 정점을 최소 비용으로 연결하여 최적 해답을 구하는 것.

알고리즘 동작 과정

1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 사이클을 형성하지 않는 간선을 선택한다.
3. 해당 간선을 현재의 MST(최소 비용 트리) 집합에 추가한다.

또한 사이클이 형성되는지 확인하기 위해서 Union-Find 알고리즘을 활용하였다.

부모 배열을 자기 번호로 초기화 시킨다음에 연결될 경우에는 더 작은 정점의 번호로 바꿔주었다.

참고 POST

크루스칼 알고리즘
유니온 파인드