프림 알고리즘의 개념

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

Spanning Tree : 그래프 내의 모든 정점을 포함하는 트리

 

최소 연결 부분 그래프이므로 간선의 수가 가장 적다.

DFS와 BFS를 사용해서 정점들을 찾기 위해 사용된 간선을 모은다. 

 

위 그림처럼, n 개의 정점이 존재할 때 (n-1)개의 간선이 연결되어있다. 

 

최소 신장 트리(MST : Minimum Spanning Tree)란,

간선의 가중치가 다를 때 최소 비용의 Spanning Tree를 선택하는 것을 말한다. 

 

MST의 특징

1) 간선의 가중치의 합이 최소

2) n개의 정점에 대해 n - 1개의 간선만을 사용

3) 사이클이 포함되서는 안된다.  

 

 

Prim MST 알고리즘이란, 

시작 정점에서 출발하여 이전단계에서 만들어진 신장 트리를 확장한다. 

 

크루스탈 알고리즘도 최소 신장 트리의 탐색에 사용된다. 

 

https://www.weeklyps.com/entry/%ED%94%84%EB%A6%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Prims-algorithm

프림 알고리즘 ( Prim's algorithm )

 

 

'T' 그래프를 간선을 통해 방문을 한 노드들을 담는다. 

이 T 그래프는 마지막 노드까지 담게되면 MST가 된다. 

 

두 가지 방법으로 프림 알고리즘을 구현한다. 

 

❗배열을 사용해 각 노드를 연결하는 최소 간선 가중치를 찾는다. 

 

https://yabmoons.tistory.com/362

[ 프림 알고리즘 ] 개념과 구현방법 (C++)