[이산수학] 프림(Prim) 알고리즘

 

 

프림(Prim) 알고리즘

---

1. 알고리즘 개요

프림 알고리즘은 임의의 그래프에서 최소 신장 트리를 찾는 알고리즘입니다. 프림 알조리즘은 그래프 꼭짓점을 중심으로 알고리즘을 전개합니다.

 

1.1. 알고리즘 동작

1. 그래프에서 임의의 꼭짓점 하나를 트리에 추가합니다.
2. 트리의 꼭짓점이 아닌 꼭짓점 중 트리에 존재하는 임의의 꼭짓점과 가장 작은 가중치의 변으로 연결된 꼭짓점을 트리에 추가합니다. 단, 기존 배치된 꼭짓점들과 연결되었을 때 사이클을 형성하면 추가하지 않고 건너뜁니다.
3. 신장 트리를 형성할 때까지 즉, 그래프 모든 꼭짓점을 포함할 때까지 2번 과정을 반복합니다.

 

2. 예시

그래프 예시

 

위와 같은 그래프가 있을 때, 프림 알고리즘으로 아래 과정을 통해 최소 신장 트리를 찾을 수 있습니다.

프림 알고리즘 예시

 

②과정에서 BD와 DE가 가중치 2로 값이 같음에도 DE를 선택하지 않은 이유는 해당 시점 트리에 변 DE로 연결되는 꼭짓점이 포함되어 있지 않기 때문입니다.

④과정에서 AD와 BC가 가중치 3으로 값이 같음에도 AD를 선택하지 않은 이유는 사이클을 형성하기 때문입니다.

---

연관 게시글

[이산수학] 그래프 - 트리

[이산수학] 그래프 - 트리

---

참조

•