프림 알고리즘

프림 알고리즘은 최소신장트리를 찾기 위한 알고리즘

방법

step 0) 임의의 정점을 선택하여 비어있는 T에 포함시킨다. (이제 T는 노드가 한 개인 트리. )

step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

step 2) 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.

step 3) 모든 노드가 T 에 포함될 때 까지, 1,2 를 반복한다.

최소신장트리는 모든 정점이 포함되어야 하므로 어느 점을 시작으로 잡아도 문제 없음

Prim 알고리즘의 시간 복잡도

1. 기본형 시간 복잡도 O(n^2)
   주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복
   Prim의 알고리즘의 시간 복잡도는 O(n^2) 이 된다.

2. 최소힙 시간 복잡도 O(ElogV)
   dist = T 에 포함된 노드에서 출발하는 간선들을 넣은 최소 힙. ( 우선순위는 가중치, 목적지 순입니다. )

   step 0) 임의의 정점을 선택하여 비어있는 T에 포함시킨다. (이제 T는 노드가 한 개인 트리. )
   step 1) T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.
   step 2) 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다.
   step 3) 모든 노드가 T 에 포함될 때 까지, 1,2 를 반복한다.

Kruskal 알고리즘의 시간 복잡도는 O(elog₂e) 이므로
그래프 내에 적은 숫자의 간선만을 가지는 ‘희소 그래프(Sparse Graph)’의 경우 Kruskal 알고리즘이 적합하고
그래프에 간선이 많이 존재하는 ‘밀집 그래프(Dense Graph)’ 의 경우는 Prim 알고리즘이 적합하다.