waca's field

# Prim의 MST 알고리즘 최소 비용 신장 트리(MST: minimum spanning tree)는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장트리를 말한다. 최소 비용 신장 트리를 이용하면, 도로 건설이나 전기 회로설계, 통신 인프라 구축 등의 문제를 가장 효율적으로 처리할 수 있게 된다. Prim의 알고리즘은 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법을 사용한다. 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함된다. Prim은 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다. 이 과정은 트리가 n - 1개의 간선을 가질 때까지 계속된다. // n개의 정점을 가지는 신장 트리의 간선은..