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

 Prim's Algorithm?

 그리디 알고리즘의 한 종류로, 임의의 점 하나를 선택 후 간선을 추가시켜 트리를 완성해 가는 알고리즘이다.

 동작 방식

 프림 알고리즘은 인접한 정점들 중 가장 최소 비용으로 연결할 수 있는 정점을 연결함.

임의의 점(p)를 선택 후, 해당 위치의 비용을 0으로 설정.
정점 p는 방문 표시 설정
for(점 p가 아닌 각 점(v)에 대해서) {
    if(간선 (p, v)가 존재하면) {
        두 정점을 연결하는 비용을 갱신
    } else {
        비용을 무한대로 설정
    }
}

while(p를 제외한 모든 정점을 방문할 때까지) {
    for(정점 p를 제외한 나머지 각각의 정점 w에 대해서) {
        w에 연결하기 위한 최소 비용으로 갱신
        정점 w 방문 표시
    }
}

 시간 복잡도

 정점의 개수가 n개라 가정하면, 

 while루프 * 각 정점에 대해서 최소값을 찾기 위해 반복문을 실행 

→ (n-1) * O(n) = O(n^2)

 

 수행 결과

 정점 1개로 시작하여 하나의 신장 트리가 완성됨.