말하는 컴공감자의 텃밭

정점과 가중치가 존재하는 간선이 주어진 상태에서 우리는 모든 정점을 가장 적은 비용으로 연결한 그래프를 최소 신장 트리라고 말한다. MST(Minimum Spanning Tree) 라고 말하며 이러한 문제에서 사용되는 알고리즘이 바로 프림과 크루스칼 알고리즘이다. 같은 목적을 지니고 있지만 접근방식이 조금 다른데 유념해서 알아보자 프림 알고리즘한 정점에서 시작해서 연결된 간선들 중 가장 가중치가 낮은 간선을 선택하며 트리를 확장하는 방식이다.시작점에서 점진적으로 최소 스패닝 트리를 완성해 나가는 그리디한 방식인데 순서는 다음과 같다.  초기화:임의의 정점을 선택해 시작한다.선택한 정점을 기준으로 연결된 간선 중 가중치가 가장 작은 간선을 선택한다.트리 확장:선택된 간선에 연결된 정점을 트리에 추가한다.이..