프림 알고리즘

프림 알고리즘의 핵심은 '어떻게 하면 비용이작은 간선들을 우선해서 찾아갈 것인가?' 가 입니다.

물론 방법은 여러가지가 될 수 있습니다만, '우선순위 큐'를 쓰면 그 고민들을 한방에 날릴 수 있습니다.

프림 알고리즘에 정말x5 아주 딱 어울리는 알고리즘 인 것 같습니다.

하지만 우선순위 큐로 작은 가중치들의 간선을 먼저 탐색 할 수 있다고해서 알고리즘이 여기서 끝나지는 않습니다. 한가지 더 고려해야 할 점 이 있습니다.

싸이클을 감지 할 수 있어야 합니다.(크루스칼 알고리즘은 union+find 알고리즘이 대표적입니다(이전 포스트 참고))

싸이클 감지에 대한 이슈를 찾아보려고 검색을 좀 했는데 잘 안나와서 직접 구현 했습니다.

원리는 다음과 같습니다.

0. 임의의 정점에서 시작하며, BFS와 비슷한 방식으로 정점을 탐색한다

1. DFS나 BFS를 구현 할 때 중복탐색을 방지하기위해 방문정보를 담는 배열을 잡습니다. (3번에서 싸이클을 감지하기위해)

2. 우선순위 큐에서 꺼낸 간선정보 안에 있는 두 정점이 방문됐다면 이 간선에 대해서는 아무런 작업을 하지않습니다. (루프진행을 하지않습니다 따라서, 큐에 다시 들어가지 않게 합니다.)

3. 큐에서 꺼낸 간선정보에서 임의의 u정점과 v정점 둘다 이미 방문됐을 경우에는 싸이클이 발생했다는 것. 예를들면,

 

위의 그래프에서 C-D와 E-D가 방문됐을 경우, ECD는 방문정보배열에서 방문됐음을 기록합니다.

따라서 다음에 EC를 방문할 경우에는 방문하지 않게 됩니다.

결과