Kruskal
가장 적은 비용으로 모든 노드를 연결할 때 사용하는 알고리즘 (MST를 만들기 위한 알고리즘)
MST 간선 개수 = 전체 노드 개수 - 1 (루프가 존재하지 않는다)
Union-Find 알고리즘 (합집합 찾기) 을 같이 사용한다.
Union-Find
여러 노드에서 두 노드를 선택해 두 노드가 같은 그래프에 속하는지 탐색
1) 모든 노드 정보가 포함된 부모 테이블을 생성한다.
2) 두 노드가 연결되면 큰 노드의 부모를 작은 노드의 부모로 변경한다.
Kruskal 알고리즘 동작 과정
1) 간선 비용에 대해 비용이 낮은 순서로 오름차순 정렬
2) 노드 간 사이클이 발생하는지 확인 (Union-Find 알고리즘 이용)
3) 사이클이 발생하면 skip, 발생하지 않으면 MST에 포함
4) 모든 간선에 대해 1~3 과정 수행
AI-Kid