[C++ 자/알 Note] Prim 알고리즘

PRIM 알고리즘과 KRUSKAL 알고리즘의 차이

KRUSKAL 알고리즘은

간선들을 정렬해서 선택하는 방식으로 진행했다

PRIM 알고리즘은 

간선들을 선택하는 것은 맞지만

탐색처럼 하나의 정점에서 시작한다

 

PRIM 알고리즘과 DIJKSTRA 알고리즘의 차이

임의의 하나의 시작점에서

간선을 하나씩 선택해 나간다는 점은 동일하다 

 

다익스트라는 현재 지점까지의 비용과 현재 지점부터 비용을

합쳐서 계산한다

반면, PRIM은 현재 지점에서 부터의 비용만을 체크해서 후보를 선정한다

 

사실상 코드는 거의 유사하며

다익스트라처럼 우선순위큐를 사용한다

 

추가적으로,

둘의 성격은 다르기에 서로 다른 곳에서 사용된다

예를 들어서

다익스트라는 여러 길 중에 최단경로를 탐색해서 사용한다

PRIM은 사이클이 발생하지 않고 최단으로 한 가지 길을 만드는 데 사용한다

 

PRIM 알고리즘 개념

1) 임의의 정점을 선택한다

2) 현재까지 선택된 정점들로부터 최소 비용의 정점을 선택한다

3) 2번 과정을 반복한다

 

위의 그림을 예를 든다면,

1) 6번을 임의의 정점으로 선택했다

2) 그리고 6번 정점에는 5번으로 가는 길과 1번으로 가는 길이 있다

그중에 가장 최소비용인 1번을 선택했다

3) 그리고 이제 반복 작업을 하면 된다

 

2) 현재까지 선택된 정점인

6번 정점과 1번 정점에 연결된 모든 간선들 중

가장 최소비용인 간선을 가진 정점을 선택하면 된다

6번 정점의 5번(25), 1번 정점의 2번(28)에서

5번을 선택하게 된다

 

한번 더 예시를 들어보면,

2) 현재까지 선택된 정점인

6번 정점, 1번 정점, 5번 정점에 연결된 모든 간선들 중

가장 최소비용인 간선을 가진 정점을 선택하면 된다

6번 정점은 더 이상 없고,

1번 정점의 2번(28), 5번 정점의 7번(24), 5번 정점의 4번(22)이 있다

이 중에 가장 최소비용인 4번을 선택하게 된다

 

이러한 과정을 반복하는 것이 PRIM 알고리즘이다

 

개념 추천 영상: https://www.youtube.com/watch?v=Qgqubl1nW7I