MST

MST(최소신장트리) - 크루스칼 & 프림 알고리즘

최소신장트리(MST / Minimum Spanning Tree)는 방향성이 없는 가중 그래프에서 간선의 가중치의 합이 최소인 신장 트리이다. 🕹️ 크루스칼 알고리즘 & 프림 알고리즘 과정 🔹 크루스칼 알고리즘 : 간선 중심으로 최소 신장 트리 구하기 (간선의 개수가 적다면 프림보다 효율적 !) 간선들의 가중치를 오름차순으로 정렬한 후 가중치가 낮은 간선부터 선택한다. 선택한 간선으로 인해 사이클이 형성된다면 다음 간선으로 넘어가고, 사이클이 형성되지 않는다면 해당 간선을 선택한다. ➔ 사이클이 형성되는지 파악하기 위해 Union-Find 연산을 진행한다. 정점이 N개인 그래프일 때, N-1개의 간선을 선택했다면 반복문을 종료한다. 🔹 프림 알고리즘 : 정점 중심으로 최소 신장 트리 구하기 (정점의 개수가..