[알고리즘]아래의 그래프에서 프림(Prim)의 최소 신장 트리 알고리즘(PrimMST)이 수행되는 과정을 단계별로 정확히 그리시오 임의의 시작점으로 점 A가 선택되었다고 가정하고 시작하시오임의의 시작점으로 점 A

목차

없음

본문내용

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

참고 자료

C언어로 쉽게 풀어 쓴 자료구조 생능출판 천인국, 고용해외
C로 배우는 알기쉬운 자료구조 인피니티북스 고응남저
코드와 그림으로 마스터하는 알고리즘 남가람북스 이상진저
위키백과 https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://swlock.blogspot.com/2016/02/prim-mstminimum-spanning-tree.html