크루스칼 알고리즘 (Kruskal Algorithm) 크루스칼 알고리즘은 최소 비용 신장 트리(MST)를 만드는 데 사용되는 알고리즘입니다. 최소 비용 신장 트리란 가장 적은 최소한의 가중치(비용)로 모든 노드를 연결한 트리입니다. 즉, 여러 장소를 최소한의 비용으로 연결하고자 할 때 적용되는 알고리즘입니다. 우선 정점(노드) vertex과 간선 edge의 개념에 대해 알고 가야합니다. 그래프 자료구조에서 자세히 다루었으니 참고하시기 바랍니다. 알고리즘 원리 크루스칼 알고리즘의 동작 원리는 다음과 같습니다. 1. 최소 비용을 기준으로 간선을 오름차순 정렬 2. 사이클 확인 후 집합 생성 (사이클이면 사이클되는 간선을 배제함) 최소 비용 신장 트리의 경우 사이클이 생성되어서는 안됩니다. 사이클 여부는 유니..