크루스칼1

• 

  [Algorithm] 크루스칼(Kruskal) 크루스칼 알고리즘에 대한 내용을 정리해보려고 합니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적 부탁드립니다! 크루스칼 알고리즘이란? 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 그리디 알고리즘으로 분류됩니다. 그렇다면 크루스칼 알고리즘에 대해서 생각해봅시다. 아래 그림과 같은 그래프를 가장 적은 비용으로 모든 노드를 연결하기 위해선 어떻게 해야할까요? 의외로 간단합니다. 간선의 비용(거리)이 적은(짧은) 순서대로 그래프에 포함시키면 됩니다. ↪ 간선 정보를 오름 차순으로 정렬하고 비용(거리)이 적은(짧은) 순서대로 그래프에 포함시키면 됩니다. 일단 위 그림과 같이 모든 간선 정보를 저장합니다. 노드 1번부터 7번까지의 모든 간선 정보를 저장한 것이고, 노드6.. Algorithm 2022. 9. 5.