최소신장 트리

최소 신장 트리(Minimum Spanning Tree, MST)는 그래프의 모든 노드를 최소의 비용으로 연결하는 부분 그래프입니다. 이는 네트워크 설계, 클러스터링, 물류 및 도로 네트워크 최적화 등 다양한 분야에서 활용됩니다. MST를 찾는 대표적인 알고리즘으로는 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 있습니다. Kotlin을 사용하여 이 두 알고리즘을 구현하는 방법을 살펴보겠습니다. 크루스칼(Kruskal) 알고리즘 크루스칼 알고리즘은 그래프의 간선을 가중치에 따라 오름차순으로 정렬한 후, 사이클을 형성하지 않는 선에서 최소 가중치를 가진 간선부터 차례대로 선택하여 MST를 구성하는 방식입니다. data class Edge(val src: Int, val dest: Int, ..