MST(Minimum Spanning Tree) MST는 최소 신장 트리로, 신장 트리를 의미하는 Spanning Tree는 그래프 내의 모든 정점을 포함하는 트리를 의미한다. 이 중 가중치가 최소가 되는 트리가 최소 신장 트리 MST 이다. MST를 구현하는 방법에는 대표적으로 Prim 알고리즘과 Kruskal 알고리즘이 있다. 여기서는 Prim 알고리즘을 사용하였다. 통신망, 도로망, 유통망 등에서 길이, 구축 비용, 전송 시간등을 최소로 구축하려는 경우 사용된다 관련 문제 백준 1197번 최소 스패닝 트리 백준 1922번 네트워크 연결 기본 개념 하나의 정점에서 시작 간선의 가중치의 합이 최소이다 사이클이 포함되어서는 안된다. 시간 복잡도 O(ElogV) --> E : 간선의 개수, V : 정점의 ..