- 현재
- 트리에 포함
- 트리와 인접
- 지금까지 최선의 간선
프림 알고리즘
프림 알고리즘은 모든 노드를 잇는 가장 저렴한 간선 집합인 최소 신장 트리를, 시작 노드에서 트리 하나를 키우는 방식으로 만듭니다. 단계마다 트리에서 가장 짧은 간선으로 닿을 수 있는 노드를 더합니다. 노드를 클릭해 거기서 시작하고, 단계를 진행하며 대기 중인 노드와 그 가장 좋은 간선, 그리고 자라는 트리를 지켜보세요. 재생을 눌러 트리가 자라는 모습을 보거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 노드를 클릭하면 시작 노드가 되고, 트리는 거기서 자랍니다. 각 간선의 숫자는 그 길이입니다. 그래프 아래에는 합류를 기다리는 노드가 트리로 이어지는 가장 좋은 간선의 길이와 함께 표시되며, 그 간선은 점선으로 그려집니다. 새 그래프는 다른 그래프를 만듭니다. 노드와 간선 수를 고를 수 있습니다. 보드를 선택한 상태에서 화살표 키는 단계 이동, 스페이스 바는 재생과 일시 정지, Home과 End는 처음과 끝으로 이동합니다.
작동 원리
- 노드를 클릭해 시작 노드로 정합니다. 트리는 거기서 자랍니다.
- 재생을 누르거나, 단계와 뒤로로 한 단계씩 이동하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다.
- 그래프 아래의 대기 중인 노드와 각 노드가 트리로 이어지는 가장 좋은 간선을 지켜보세요. 새 그래프로 다른 그래프를 시도할 수 있습니다.
프림 알고리즘의 작동 방식
노드 하나로 된 트리에서 시작합니다. 트리 밖의 모든 노드는 트리로 이어지는 가장 짧은 간선이 있으면 그것을 기억합니다. 간선이 가장 짧은 노드를 골라 그 노드와 간선을 트리에 더하고, 그 노드의 간선을 살펴보는 일을 반복합니다. 어떤 간선이 이웃 노드의 지금까지 최선의 간선보다 짧으면, 그것이 그 이웃의 최선의 간선이 됩니다. 모든 노드가 합류하면 트리의 간선 수는 노드 수보다 하나 적고, 총길이는 가능한 한 작습니다.
프림과 다익스트라
프림 알고리즘과 다익스트라 알고리즘은 거의 똑같아 보입니다. 둘 다 시작 노드에서 영역을 넓혀 가며 대기 중인 노드를 우선순위 큐에 둡니다. 차이는 큐에 든 숫자입니다. 다익스트라는 각 노드의 시작 노드로부터의 전체 거리를 두고, 프림은 트리로 이어지는 가장 좋은 간선 하나의 길이만 둡니다. 그래서 다익스트라는 최단 경로 트리를, 프림은 총길이가 가장 작은 트리를 만들며, 두 트리는 자주 다릅니다.
자주 묻는 질문
프림 알고리즘이란 무엇인가요?
시작 노드에서 트리 하나를 키우면서, 트리와 트리 밖의 노드를 잇는 가장 짧은 간선을 항상 더해 가중 그래프의 최소 신장 트리를 만드는 그리디 알고리즘입니다.
시작 노드가 중요한가요?
순서에만 영향을 줍니다. 어느 시작 노드에서든 프림 알고리즘은 똑같이 가장 작은 총길이의 신장 트리로 끝납니다. 길이가 같은 간선이 있으면 트리 자체는 달라질 수 있습니다.
프림 알고리즘은 누가 만들었나요?
보이테흐 야르니크(Vojtěch Jarník)가 1930년에 처음 설명했습니다. 1957년 로버트 프림(Robert Prim), 1959년 에츠허르 다익스트라(Edsger Dijkstra)가 다시 발견했기 때문에 야르니크 알고리즘 또는 프림–야르니크 알고리즘이라고도 합니다.
프림 알고리즘은 얼마나 빠른가요?
이진 힙을 쓰면 노드 V개, 간선 E개에 대해 작업량이 E log V에 비례해 늘어납니다. 힙 대신 단순한 배열을 쓰면 약 V² 단계가 걸리는데, 거의 모든 노드 쌍이 연결된 밀집 그래프에서는 이쪽이 더 낫습니다.
내 그래프가 어딘가로 전송되나요?
아니요. 그래프와 트리는 브라우저 안에서 만들어지며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동