최소 비용 스패닝 트리 - Prim알고리즘

최소 비용 스패닝 트리

그래프의 서브 그래프 중에 모든 vertex를 가지고 있고, edge를 가지는 것을 스패닝 트리라고 한다.

가중치가 있는 그래프에서 이러한 스패닝 트리 중에서 최소 비용인 것을 최소 비용 스패닝 트리라고 한다. 

신장 트리의 중요한 요건

하나, 순환이 되어서는 안 된다.

잠시만!!

최소 비용 스패닝 트리는 실제로 어디에 쓸 수 있을까? 맹목적으로 알고리즘을 배우고 외우는 것 보다 어디에 쓰일 수 있는지에 대해서 알면 좀 더 필요서이 생길 것 같다. 

필요한 상황에 대해서 한 번 예를 들어보겠다. 우리가 위치기반 서비스를 통해 가장 서울 지역 관광 명소를 현재 위치를 기반으로 최소의 거리 비용으로 돌 수 있는 서비스를 만들고 있다고 쳐보자.

위의 경우에 우리는 최소의 비용으로 관광지를 모두 돌 수 있는 알고리즘이 필요하다. 이러한 상황에서 최소 비용 스패닝 트리 알고리즘을 적용 해 볼 수 있을 것이다.

최소 비용 스패닝 트리를 구하기 위한 몇 가지 용어들에 대해서 알아두어야 한다.

트리(tree)정점 : 지금까지 만든 트리에 속하는 정점

주변확인(fringe) 정점 : 트리에는 속하지 않고, 트리에 속한 정점과 인접한 정점

미확인(unseen) 정점 : 나머지 정점들

프림(Prim) 알고리즘

모든 정점을 미확인 정점으로 초기화한다.

임의의 정점 s를 출발정점으로 한다. 

s에 인접한 모든 정점을 주변 정점으로 둔다. 

while(주변 정점이 있으면)

{

트리 정점 t와 주변 정점들 사이의 최소 가중치를 가진 에지 tv를 선택한다.

v를 트리 정점으로 둔다. 에지 tv를 트리에 추가한다.

v에 인접한 모든 미확인 정점을 주변정점으로 한다. 

}

다음의 그래프를 통해 prim알고리즘을 통해 greedy한 방법으로 최소비용스패닝트리를 구하는 과정을 설명하겠다.