[개념 정리] 최소 신장 트리 (Minimum Spanning Tree, MST) 정리

이번에는 최소 신장 트리(Minimum spanning tree, MST)에 대해서 정리해 보도록 하겠습니다. 우선 글의 정리 순서는 다음과 같습니다. Spanning Tree Spanning Tree의 특징 MST(Minimum spanning tree)란? MST 구현 방법 크루스칼(Kruskal) 알고리즘 방식 구현 소스 코드 프림(Prim) 알고리즘 방식 구현 소스 코드 MST (Minimum Spanning Tree), 최소 신장 트리를 알아보기에 앞서 우선 Spanning tree의 개념부터 정리해 보도록 하겠습니다. Spanning Tree 최소 신장 트리 (Spanning Tree): 그래프 내의 모든 정점을 포함하는 트리를 의미합니다. Spanning tree는 그래프의 최소 연결 트리입니다. 여기서 최소 연결은 간선의 수가 가장 적음을 의미하고, 예를 들어 n개의 정점을 잇는 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되면 필연적으로 tree의 형태...