반응형
크루스칼
-
[알고리즘] Kruskal 알고리즘알고리즘 2021. 12. 2. 14:53
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. Kruskal 알고리즘이란 그래프의 간선에 비용이 있는 경우 해당 그래프이 모든 정점을 연결하는 최소 비용으로 연결하는 최소비용 신장트리를 찾는 알고리즘 입니다. 신장트리 그래프의 모든 정점을 포함하고 정점들은 간선으로 연결되어 있으면서 사이클이 존재하지 않는 그래프를 말합니다. 위 이미지의 그래프가 그래프의 신장트리가 됩니다. 수많은 신장트리 중에서 연결된 간선의 비용이 최소가 되는 신장트리를 바로 최소비용 신장트리라고 하며 Kruskal 알고리즘을 통해 해당 그래프를 찾을 수 있습니다. 2. Kruskal 알고리즘 고려사항 최소 비용의 간선을 선택하는 과정을 ..