크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 즉, 크루스칼 알고리즘은 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이다. 그림과 같은 그래프에서 정점은 7개, 간선은 11개 이다. 가장 적은 비용으로 모든 노드를 연결하는 최소 비용 신장 트리를 만들 때 사용되는 간선의 개수는 6개 이다. 즉, 최소 비용 신장 트리를 만들 때 사용되는 간선의 개수는 노드 개수 -1 이다. 최소 비용 신장 트리는 거리를 기준으로 오름차순 정렬을 한 후 그래프를 연결함으로써 만들 수 있다. 주의할 점은 정렬된 순서에 맞게 그래프에 포함시키기 전에 사이클이 형성되면 안된다. 그렇기 때문에 사이클 테이블을 먼저 확인한 후, 만약 사이클을 형성하는 경우에는 간선을 포함하지 않도록..
