'2016/09/24'에 해당되는 글 2건

  1. 2016.09.24 [알고스팟] 남극기지 > 최소신장트리 (MST) > 프림 알고리즘
반응형

문제: 남극기지


이 문제는 최소신장트리 문제이다. 각 기지를 연결하는 최소 신장 트리에서 각 기지간의 연결 거리 중 가장 큰 값을 찾으면 된다.


이전 포스팅 에서는 Kruskal 알고리즘을 이용해서 문제를 풀었었는데, 본 포스팅에서는 Prim 알고리즘을 이용해서 풀어보겠다.


 프림 알고리즘은 다음과 같이 동작한다.

  1) 시작점을 선택하고 시작점을 추가된 정점의 집합인 MST_V 에 추가한다.

  2) MST_V에 속해 있는 정점과 그렇지 않은 정점 중 최소 간선을 가지는 정점을 MST_V에 추가한다.

  3) 2)를 모든 정점이 MST_V에 들어가게 될 때까지 방복한다.


다음 그림에서 상세하게 설명한다.



다음은 PriorityQueue를 이용해서 구현한 버전이다.




다음은 정점을 추가할때 다른 정점들과의 거리의 최소값을 저장해서 구현한 버전이다. 다음 그림처럼 MST_V 에 추가된 정점들이 있을 경우에 이 정점들로부터 그 외 정점들까지의 최소 비용을 Update하는 매트릭스를 이용해서 계산한다.


다음은 이를 구현한 코드이다.


반응형
Posted by alias
,