프림 알고리즘(Prim's Algorithm)

프림 알고리즘
간선의 가중치가 있고
간선의 방향이 없는 무향간선
가중치 있는 무향그래프에서 최소 비용 트리를 찾는 알고리즘임.

최소 신장 트리 MST ; Minimal Spanning Tree 
주어진 그래프에서 모든 정점을 포함, 각 간선의 비용의 합이 최소가 되는 부분 그래프-트리를 의미.

프림 알고리즘
1) 그래프에서 아무 정점 A 선택함.
2) 그 정점 A을 방문표시함.
3) 1)에서 선택한 정점 A에서 이어진 모든 간선 중 가중치가 가장 작은 간선을 이으며,
  이어진 정점 B 에도 방문표시!
  해당 정점 B 에 이어진 간선까지 모두 본다. 
4) 이제 3번과정을 반복한다. 
  그런데 이어진 정점들의 모든 간선들 중 가중치가 가장 작은 간선이지만,
 정점이 방문되어 있다면 간선을 잇지 않음.
 정점이 방문되어 있지 않다면 간선을 이음.

위 과정을 반복하는 건데 
내가 이해하는 바로 쉽게 말하면, 
정점하나 지정하고 거기서부터 이어져 있는 간선 중 가중치 제일 작은 애들만 이어나가
그런데 제일 작은 거를 이으려고 하는데 ? 이으려는 간선이 방문되어 있어? 그럼 하지말고 
다음으로 큰 간선찾아서 계속 해보자! 모든 정점을 연결했으면 그만두자!

이게 내가 이해한 바임.

 

 

위와 같이 그래프가 주어졌다고 했을 때 
정점5 부터 시작한다고 해보자.

 

그럼 정점5번과 연결되어 있는 간선이 
가중치 
1인 간선 (정점 2, 8 과 연결) 
3인 간선 (정점4와 연결) 
5인 간선 (정점6과 연결)

그러면 이 중에서 가장 작은 간선을 연결 시킨다.
가중치가 같은 경우에는 정점번호가 낮은 것 부터 연결한다고 하자 

 

사용한 간선은 검정색, 
남아있는 간선은 빨간색, 
실제 그래프에 연결되어있는 간선 하늘색(아직 본적없는 간선)

그렇다면 정점2 와 연결이 되고 
간선이 두개가 추가된다.
정점2와 연결된 가중치
1인 간선 ( 정점 3과 연결 )
2인 간선 ( 정점 1과 연결 )
그럼 이때? 가중치 1인게 또 두개 있으니 작은 정점을 연결 시킴. 그럼 정점 3과 연결시킨다.

 

 

 

그러면 가중치 
1인 간선 (정점 6과 연결)
6인 간선 (정점 10과 연결)
된 간선이 추가되고 또? 가중치 1인 간선이 두개 있으니까 낮은 정점 (6,8중) 정점 6번을 연결시킨다.

 

 

그러면 정점 6번까지 연결했고,
가중치가 7인 간선이 추가(정점 9와 연결)
그러면 이제 가중치 1인게 하나 뿐이니까 드디어 정점8과 연결시키자!

 

이제 가중치 4 (정점 7 연결) , 7 (정점 9 연결) 인 간선이 추가되었고!
빨간 선들 중 가장 작은게 보면.............. 가중치 2인게 제일 작다!
저거 연결 시킴. 그럼 정점 1을 연결시킨다!

 

 

그러면 또 가중치 1인 (정점 4 연결) 간선이 추가되었으니 저거를 먼저 연결하자!

 

 

 그러면 또 가중치 1인 간선(정점 7 연결) 이 생겼으니 연결하자!

 

 그러면 빨간색이 많은데 
정점이 빨간색인 것들은 방문한 정점이라는 것이고!
빨간색 간선은 탐지되었지만 사용하지 않았다는 얘기가 되는 것이고

가중치가 낮은 순서대로 나열을 해보면
가중치 정점(A-B)연결
3 (4-5)
4 (7-8)
5 (5-6)
6 (3-10)
7 (6-9)
7 (8-9)
근데 이게 사실상 간선을 추가한 정점 그러니까 간선의 출발정점?
처음의 경우로 얘기를 하면

간선을 추가시킨 정점 5 의 정보는 필요 없고, 도착 정점과 가중치 값만 있으면 최소값은 구할 수 있다.

뭐 일단 저 문제풀때는 이런거 제외하고 ...

 

 

다시 돌아와서...
가중치가 낮은 순서대로 나열을 해보면
가중치 정점(A-B)연결
3 (4-5) 모두 방문함
4 (7-8) 모두 방문함
5 (5-6) 모두 방문함
6 (3-10) 연결 시켜야함! 
7 (6-9) 대기
7 (8-9) 대기
상태가 된다.
그러면 

이런 형태가 되고 
낮은 정점부터 연결한다고 얘기했으니까 6-9 가중치 7 인 간선을 연결 시키면 끝난다!

그리고 나머지 간선은 사용하지 않으니 버리고 

 

이런 꼴이 되는데 MST만 보게 되면

 

 

이런 꼴이 나오게 된다.

어느 정점에서 시작하건 동일하게 나오므로... 

이제 여기서 사용할 자료구조에 대해서 얘기를 하면 무조건 최소인 가중치를 뽑아야하니까 
우선순위큐로 Min-Heap을 사용해야 한다.

그리고 저 경우를 보기 위해서 우선순위 큐가 모두 비어 질 때 까지 과정을 반복하면 최소값을 구할 수 있다. 

 

 

012345678910111213