프림(Prim)의 MST 알고리즘 Prim 알고리즘은 특정 정점에서 시작해 신장 트리 집합을 단계적으로 확장해 나가는 방법입니다. 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택해 트리를 간선이 $n-1$개가 될 때까지 확장합니다. 최소 신장 트리 구하는 과정 예시로 한 그래프에서 Prim 알고리즘을 이용해 MST를 구해보도록 하겠습니다. 시작 정점은 0이라고 가정하겠습니다. 결론적으로 이 그래프의 최소 신장 트리는 마지막 사진에 색칠한 것과 같이 이루어짐을 알 수 있습니다. 코드로 구현하면 아래와 같습니다. typedef struct Graph { int n; // 정점의 개수 int weight[MAX_VERTICES][MAX_VERTICES]; } Graph; int selected[MAX_..