[최소 신장 트리] 프림[Prim] 알고리즘

최소 신장 트리란?

주어진 그래프의 모든 정점을 연결하는 부분 그래프 중에서

그 가중치의 합이 최소인 트리이다.

 

최소 신장 트리를 구하는 방법은 여러 가지가 있다.

그중에 프림 알고리즘에 대해 알아보자.

 

프림 알고리즘은 그리디 알고리즘이다. 

 

동작 순서

1. 그래프에서 임의의 정점을 선택하여 집합 A에 넣는다.

2. 그 정점과 연결된 변들을 집합 B에 넣는다.

3. 집합 B에서, 변의 양쪽 정점이 모두 집합 A에 있지 않은 것 중에 가장 가중치가 작은 변을 찾는다. 

4. 3번에서 찾는 변의 양쪽 정점 중 집합 A에 없는 정점을, 집합 A에 넣는다.

 

모든 정점이 집합 A에 들어올 때까지 2~4번을 반복한다. 

 

 

https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html

 

 

알고리즘이 종료됐을 때 만들어진 트리는 최소 신장 트리가 된다.

아래는 코드이다.

 

https://sojeong-lululala.tistory.com/88

[BOJ] [Python] 1197 : 최소 스패닝 트리