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

크루스칼(Kruskal)의 MST 알고리즘 Kruskal 알고리즘은 탐욕적인 방법(Greedy, 그리디)를 사용합니다. 그리디를 간략하게 설명하자면, 선택할 때마다 그 순간 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방법입니다. 그리디는 근사적인 방법이기 때문에 항상 최적의 해답을 주지 않을 수도 있습니다. 하지만 Kruskal의 MST 알고리즘은 최적의 해답을 주는 것으로 증명되었기 때문에 이 방법으로 최적해(최단 경로)를 구할 수 있습니다. 알고리즘의 작동 방식은 다음과 같습니다. 그래프의 간선들을 가중치의 오름차순으로 정렬함 사이클을 형성하지 않는 간선을 찾아서 최소 신장 트리의 집합에 추가함 가장 낮은 가중치를 가진 간선을 먼저 선택함 만약 사이클을 형성하는 간선이 있다면 그..