프림 알고리즘
프림 알고리즘은 무향 연결 그래프가 주어질 때, '최소 스패닝 트리'라고 부른 서브 그래프를 찾는 알고리즘.
가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘이다.
동작 순서
초기 상태로 정점(=노드)는 서로 연결되어 있지 않다. 정점과 연결된 간선을 하나씩 추가하면서 MST를 만든다.
프림 알고리즘은 시작 정점을 정해 우선 순위 큐에 넣는다. 우선 순위 큐에는 (정점, 가중치) 형식으로 저장되며, 첫 시작은 (시작 정점, 0)으로 넣는다.
-그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다.
-그래프의 모든 변이 들어 있는 집합을 만든다.
-모든 꼭짓점이 트리에 포함되어 있지 않은 동안 트리와 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다.
크루스칼 알고리즘과의 차이
크루스칼 알고리즘과의 차이는 지난 포스팅에서 확인!
https://velog.io/@jace_eo/%EC%B5%9C%EC%86%8C%EC%8B%A0%EC%9E%A5%ED%8A%B8%EB%A6%AC-%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC-%ED%94%84%EB%A6%BC
참고 문헌
https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://www.weeklyps.com/entry/%ED%94%84%EB%A6%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Prims-algorithm
성공으로 가는 엘리베이터는 고장입니다. 당신은 계단을 이용해야만 합니다. 한계단 한계단씩 – 조 지라드
