원더랜드(프림)

안녕하세요, 인프런 AI 인턴입니다.

님께서 프림 알고리즘과 다익스트라 알고리즘을 비교하며 헷갈리시는 부분이 있는 것 같아 이에 대해 설명드리겠습니다.

프림(Prim) 알고리즘과 다익스트라(Dijkstra) 알고리즘은 둘 다 우선순위 큐를 활용하여 그래프를 탐색하지만, 각 알고리즘의 목적과 동작 방식은 다소 다릅니다.

프림 알고리즘의 목적:
- 프림 알고리즘은 최소 스패닝 트리(MST)를 찾기 위한 알고리즘으로, 그래프의 정점을 모두 연결하는 최소 비용을 찾는 것이 목표입니다.
프림 알고리즘의 동작 원리:
- 시작 정점에서 연결된 간선을 기준으로 최소 비용(가장 작은 가중치)의 간선을 선택하여 트리를 구성합니다.
- 우선순위 큐는 최소 가중치 간선을 선택하기 위해 사용되며, 이는 항상 ‘현재까지’의 최적의 선택을 보장합니다.
- 동작 중 선택된 간선은 MST의 일부가 되며, 이는 다른 노드로의 최소 비용 연결을 계속해서 보장하기 때문입니다.
초기 정점의 선택:
- 프림 알고리즘은 그래프가 연결 그래프라는 기본 가정 하에 작동하므로, 초기 정점의 선택은 결과에 영향을 미치지 않습니다. 어떤 정점에서 시작하든지 최소 스패닝 트리를 만들 수 있습니다.

프림 알고리즘에서 pQ.poll()된 정점은 최소 가중치로 연결된 정점임을 보장합니다. 이 과정은 다익스트라와 본질적으로 유사하지만, 다익스트라는 특정 출발점에서 모든 정점으로의 최단 경로를 찾는 목적이기 때문에 프림과의 목적 차이를 이해하시면 도움이 될 것 같습니다.

관련 질문에 대해 좀 더 깊이 이해하고자 하는 경우, 아래의 답변을 참고해 보시면 도움이 될 것입니다:
- 그래프 최단거리(BFS) 질문이 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변