알고리즘 설명 프림 알고리즘(Prim, 최소 신장 트리, MST) KQNG 2018. 7. 17. 17:20 이웃추가 본문 기타 기능 이번 포스트에서는 최소 신장 트리를 구현하는 알고리즘인 프림 알고리즘에 대해서 설명해보도록 하겠습니다. 프림 알고리즘은 정점 하나를 기준으로 삼아 연결된 다른 점으로 갈 때 가장 적은 비용이 드는 점과 선으로 이어주며 진행해나가는 알고리즘입니다.
다음과 같은 정점들과 각 정점들을 있는 선들의 비용이 주어지면 Prim 알고리즘의 진행과정은 다음과 같습니다. (a) 우선 1번 정점을 기준으로 삼으면 2번으로 가는 비용은 1, 3번으로 가는 비용은 4, 4번으로 가는 비용은 5가 듭니다.
따라서 가장 비용이 적은 2번으로 선을 그려줍니다. (b) 1번과 2번을 기준으로 모든 점을 가는 비용을 살펴봅니다. 1번에서 3번으로 가는 비용은 4, 1번에서 4번으로 가는 비용은 5 2번에서 3번으로 가는 비용은 2, 2번에서 4번으로 가는 비용은 6이 듭니다.
따라...
#
MST
#
프림
#
프로그래밍
#
코딩
#
최소신장트리
#
최소스패닝트리
#
알고리즘설명
#
알고리즘
#
PRIM
#
프림알고리즘
원문 링크 : 프림 알고리즘(Prim, 최소 신장 트리, MST)
