최소 신장 트리(MST)를 구성하는 알고리즘으로 무엇을 선택하는가?

가중치 합이 최소가 되는 신장 트리를 찾기 위해 크루스칼이나 프림 알고리즘을 선택한다. 데이터의 밀집도에 따라 선택 기준이 달라진다.

크루스칼 알고리즘은 간선 위주로 선택한다. 가중치가 낮은 간선을 우선적으로 연결하며, 사이클이 발생하지 않는지 Union-Find로 검사한다.

프림 알고리즘은 정점 위주로 선택한다. 트리 안과 밖을 잇는 간선 가운데 가중치가 가장 작은 것을 골라 그 바깥 정점을 끌어들인다. 정점이 아니라 간선의 가중치를 본다.

간선 수가 적은 희소 그래프에서는 크루스칼이 구현과 계산 면에서 유리하다. 반면 정점 수가 많고 간선이 빽빽한 밀집 그래프에서는 프림이 유리하다.