프림 알고리즘
발전소에서 케이블을 까는 상황을 떠올려 보세요. 가장 가까운 마을을 먼저 잇고, 그다음 이미 연결된 어느 곳에든 가장 가까운 마을을 잇는 식으로 계속합니다. 이것이 프림 알고리즘이며, 언제나 가장 저렴한 네트워크로 끝납니다.
아이디어
최소 신장 트리는 가중 그래프의 모든 노드를 가능한 가장 작은 간선 길이 합으로 연결합니다. 프림 알고리즘은 시작 노드에서 바깥으로 트리 하나를 키워 이것을 만듭니다. 트리는 결코 여러 조각으로 나뉘지 않습니다. 단계마다 트리에서 나가는 가장 짧은 간선으로 정확히 새 노드 하나가 합류합니다.
단계별 설명
시작 노드를 트리에 넣습니다. 트리 밖의 각 노드에 대해 가장 좋은 간선, 즉 트리 안의 어느 노드로든 이어지는 가장 짧은 간선을 기억합니다. 그리고 반복합니다. 가장 좋은 간선이 가장 짧은 바깥 노드를 골라 그 간선과 함께 트리에 더하고, 그 노드의 간선을 살펴봅니다. 트리 밖의 이웃 노드가 이제 더 짧은 간선으로 닿을 수 있으면, 그 간선이 새로운 가장 좋은 간선이 됩니다. 모든 노드가 트리에 들어가면 멈춥니다.
예제
길이 1인 A–B, 2인 B–C, 3인 A–C, 4인 C–D, 5인 B–D 간선이 있고, A에서 시작합니다. A의 간선으로 B는 가장 좋은 간선 1을, C는 3을 얻습니다. B가 가장 가까우므로 A–B로 합류하고, B의 간선으로 C는 2로 좋아지고 D는 5를 얻습니다. C가 B–C로 합류하고, 그 간선 C–D로 D는 4로 좋아집니다. 마지막으로 D가 C–D로 합류합니다. 트리 A–B, B–C, C–D의 총길이는 1 + 2 + 4 = 7입니다.
옳은 이유
단계마다 노드는 트리 안과 트리 밖의 두 그룹으로 나뉩니다. 컷 속성에 따르면 이런 두 그룹 사이의 가장 짧은 간선은 항상 어떤 최소 신장 트리에 속합니다. 프림은 언제나 정확히 그 간선을 더하므로, 지금까지 만든 트리는 언제나 최소 신장 트리로 완성될 수 있고, 모든 노드가 합류하면 그것이 최소 신장 트리입니다.
역사와 속도
체코의 수학자 보이테흐 야르니크(Vojtěch Jarník)가 1930년에 이 알고리즘을 발표했습니다. 로버트 프림(Robert Prim)이 1957년 벨 연구소(Bell Labs)에서 다시 발견했고, 에츠허르 다익스트라(Edsger Dijkstra)가 1959년에 또다시 발견했습니다. 대기 중인 노드를 이진 힙에 두면 노드 V개, 간선 E개에 대해 작업량이 E log V에 비례해 늘어납니다. 단순한 배열을 쓰면 약 V²로, 거의 모든 노드 쌍이 연결된 경우에 더 낫습니다. 피보나치 힙을 쓰면 E + V log V입니다.
직접 해 보기
앱을 열고 노드를 클릭해 거기서 시작한 다음 단계를 누르세요. 트리 안의 노드는 초록색, 대기 중인 노드는 파란색이고, 대기 중인 각 노드의 가장 좋은 간선은 점선으로 그려집니다. 대기 중인 노드는 가장 좋은 간선의 길이와 함께 짧은 순서로 그래프 아래에 표시되며, 맨 앞의 노드가 다음에 합류합니다. 여러 노드에서 시작해 보며, 순서는 바뀌어도 총길이는 그대로인 것을 확인해 보세요.
자주 묻는 질문
프림 알고리즘과 다익스트라 알고리즘은 어떻게 다른가요?
둘 다 우선순위 큐로 시작 노드에서 영역을 넓혀 갑니다. 프림은 대기 중인 노드를 트리로 이어지는 가장 좋은 간선 하나의 길이로 줄 세우고, 다익스트라는 시작 노드로부터의 전체 거리로 줄 세웁니다. 프림은 최소 신장 트리를, 다익스트라는 최단 경로 트리를 만듭니다.
프림 알고리즘은 음수 간선 길이에서도 작동하나요?
네. 다익스트라 알고리즘과 달리 프림은 간선끼리만 비교하므로 음수 길이가 있어도 문제가 없습니다. 여전히 총길이가 가장 작은 신장 트리를 찾습니다.
그래프가 연결되어 있지 않으면 어떻게 되나요?
프림 알고리즘은 닿을 수 있는 모든 노드에 도달하면 멈추므로, 시작 노드가 있는 조각의 최소 신장 트리만 얻습니다. 아직 닿지 않은 노드에서 다시 실행하면 최소 신장 포레스트를 얻습니다.
프림과 크러스컬 중 어느 알고리즘이 더 좋나요?
어느 한쪽이 항상 이기지는 않습니다. 프림은 밀집 그래프와 이웃 목록으로 저장된 그래프에 알맞고, 크러스컬은 간선 목록으로 주어진 희소 그래프에 알맞습니다. 둘 다 같은 총길이의 트리를 찾습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
프림 알고리즘 해 보기