12.4 크루스칼 알고리즘이번에는 크루스칼 알고리즘으로 최소신장트리를 만드는 방법을 알아봅시다. 프림 알고리즘은 최적의 정점을 선택하여 최소신장트리를 만드는 방법입니다. 반면 크루스칼 알고리즘은 최적의 간선을 선택하여 최소신장트리를 만드는 방법입니다. 크루스칼 알고리즘선택한 간선 0으로 설정원본 그래프의 간선 집합을 복제복제한 간선 집합을 비중 순으로 정렬반복(선택한 간선 개수가 graph의 정점 개수-1 보다 작다면) 조건(탐욕스런 간선을 선택이 실패 반복문 탈출 아니면 선택한 간선 개수 1 증가 최적의 간선은 비중이 작은 간선 중에 선택합니다. 그런데 선택한 간선을 현재까지 만들고 있는 그래프(최소신장트리)에 추가하였을 때 사이클이 발생하지 말아야 합니다. 이를 효과적으로 구현하기 위해 원본 그래프의..
