알고리즘에서 '크루스칼(Kruskal)' 알고리즘과 '프림(Prim)' 알고리즘의 공통점과 차이점은?

해설

크루스칼과 프림 모두 그리디 알고리즘으로 최소 신장 트리를 구합니다. 크루스칼은 모든 간선을 가중치 순으로 정렬한 후 사이클이 생기지 않는 간선을 순서대로 추가합니다(Union-Find 활용). 프림은 하나의 정점에서 시작하여 연결된 간선 중 최소 가중치를 선택하며 트리를 확장합니다.