[알고리즘] Kruskal 알고리즘

개념

탐욕법(greedy algorithm)을 이용하여 네트워크(가중치가 있으면서 방향이 존재하는 그래프)의 모든 노드를 잇는 최소 비용을 구하는 알고리즘

과정

① 간선들을 가중치의 오름차순으로 정렬
② 정렬된 간선들을 하나씩 선택하되 사이클을 형성하지 않는 간선만 선택
③ 해당 간선을 현재 MST 집합에 추가

전 과정에 걸쳐 최솟값을 하나씩 MST 집합에 포함시켜 나가다가(safe edge : 추가시켜도 트리의 형태가 유지) 사이클이 형성되는 경우 선택하지 않는다(추가하고자 하는 간선의 노드가 같은 집합에 포함되어 있는지)

알고리즘의 사용

프로그래머스 - 섬 연결하기

전형적인 최소 비용 신장 트리 문제면서 Kruskal 알고리즘을 사용하라고 대놓고 알려주는 문제이다.(사실 막혔음)