크루스칼 알고리즘
그래프 이론에서 모든 노드 정점을 연결하는 방법입니다. 최소 스패닝트리 라고도 불립니다. 가장 비용이 적은 간선부터 이미 연결돼 있는 노드인지 확인하며 트리를 완성합니다. 아래는 작은 그래프 예시를 들었습니다. 최소 스패닝트리 1, 2를 보시면 최소 비용 4로 모두 동일하지만 그래프 모양은 다릅니다. 이처럼 경우에 따라 스패닝트리가 여러개 있을 수 있습니다.
알고리즘 구현
이를 코드로 구현하는 법은 비유하자면 다음과 같습니다. 전국 일주 경로를 짜야할 때 각 지역을 연결하는 운송수단과 비용이 적힌 티켓이 있습니다. 이를 최소한의 비용으로 모든 지역을 연결하려면 전국지도를 펼쳐 놓고 낮은 비용의 티켓순으로 정렬한 후 티켓에 적힌 출발지 목적지를 지워가며 경로를 짭니다. 물론 어디까지나 구현 방법을 쉽게 이해하기 위한 비유일 뿐 엄밀하지는 않습니다. (같은 지역 재방문, 출발 지역은 어디든 상관없음)
티켓 <=> Class Node{ int from, to, cost }
추천 문제
[백준 1197번 최소스패닝트리] https://www.acmicpc.net/problem/1197