[DATA STRUCTURES - Graph] Prim Algorithm — “정점 중심” Greedy MST

Prim 알고리즘은 정점 중심이다.

Kruskal 은 간선 중심으로, 가중치로 정렬을 했을 때

Prim 은 선택한 정점의 집합에서 , 아직 선택되지 않은 정점으로 나가는 간선 중에 가중치가 가장 작은 간선을 선택한다.

 

 

 

 

Kruskal 과 다르게 Cycle 검사가 필요 없다. 
새로운 후보 간선들 중, 가중치 작은 간선을 선택할 때

해당 후보들은 다 "선택되지 않은 정점으로 나가는 간선" 들이기 때문이다! 

 

 

 

 

select v such that (u, v) is the smallest edge where u ∈ V_new, v ∉ V_new;

현재 트리에 포함된 정점 집합인 V_new 에서 밖으로 나가는 정점들을 본다! v는 V_new에 있으면 안된다. 

새 정점 v를 트리에 편입시키는 최소 간선을 고르는 것임. 

 

여기서 

“V_new에서 밖으로 나가는 간선”이 없다는 뜻은?

• V_new 집합은 연결되어 있는데, 남은 정점들은 완전히 끊겨 있음 -> 연결 그래프가 아니라 MST 를 만들 수가 없다.