[알고리즘]최소신장트리-크루스칼 알고리즘

크루스칼 알고리즘 크루스칼 알고리즘은 일단, 모든 간선의 가중치를 오름차순으로 정렬을 합니다. 이후에 간선의 가중치가 적은 간선부터 차례대로 신장트리 조건에 충족할때까지 최소신장트리에 추가해가는 방식 입니다. 정리하면 아래와 같습니다. 그래프의 모든 간선을 가중치 기준으로 오름 차순 정렬 합니다. 가중치가 낮은 간선부터 최소신장트리에 하나씩 추가합니다.(사이클을 형성하지 않아야 합니다) “2.”의 과정을 신장트리 조건에 충족할때까지 반복 합니다. 1단계 간선의 가중치를 기준으로 오름차순 정렬한 데이터를 하나 생성 했습니다. start와 end는 간선의 양끝을 나타냅니다.(방향이 없으므로 start와 end는 서로 바뀌어도 무방합니다) value는 간선의 가중치를 나타냅니다. 2단계 가중치가 제일 낮은 간선의 가중치부터 확인 합니다. 정점{2,3}을 잇는 간선을 최소신장 트리에 추가 합니다. 3단계 가중치가 제일 낮은 간선의 가중치부터 확인 합니다. 정점{3,6}을 잇는 간선을 최소신...

원문링크 : [알고리즘]최소신장트리-크루스칼 알고리즘