MST 썸네일형 리스트형 최소신장트리 MST: Prim's algorithm 프림알고리즘은 최소신장트리, MST(minimum spanning tree)를 찾는 알고리즘이다.최소신장트리 는 무향그래프의 모든 정점을 잇는 신장트리 중 그 가중치의 합이 최소인 그래프이다.알고리즘은 다음과 같다.(1) 시작할 정점을 선택한다. 아무 정점이나 선택해도 된다.(2) 선택한 정점에서 갈 수 있는 다른 정점 중 가장 가중치가 작은 정점을 선택해 잇는다.(3) 이어진 정점들에서 갈 수 있는 정점 중 가장 가중치가 작은 정점을 선택해 잇는다.(4) 모든 정점을 선택할 때 까지 (3)과정을 계속 반복이어진 정점이라고 표기했는데 선택한 정점이 최소신장트리에 포함되는 것이며,지금까지 선택한 모든 정점들에서 선택하지 않은 정점까지의 가중치가 가장 작은 것 을 선택하는 것이다.작은 것들만 선택하는 것에서.. 더보기 이전 1 다음