프림(Prim) MST 알고리즘

크루스칼과 같은 최소 스패닝 트리를 구하는 알고리즘.

 

크루스칼 알고리즘은 탐욕(greedy)적인 방법으로 작은 가중치의 간선만을 선택해서 사이클이 발생하지 않는다는 가정하에 간선을 붙여줬다.

 

프림 알고리즘의 특징은 하나의 시작점(어느 정점이든 상관x)으로 구성된 트리에 간선을 하나씩 수집하며 진행한다.

네모가 쳐진 정점을 기준으로 15와 35라는 간선을 선택할 수 있는데.

당연히 15가 더 적은 가중치를 가진 간선이니 15를 선택한다.

 

이제 그 다음 정점을 확인해보면 5,10이라는 가중치를 가진 간선들.

더 작은 5 간선을 선택하고. 10이라는 간선을 확인했을때. 시작정점을 기준으로 15 + 10 = 25이니. 35보다 작다는것을 알 수 있음. 그러므로 35는 선택이 불필요.

 

이런식으로 나머지 간선도 선택을 해내간다.

 

다익스트라와 같이 간선을 최소 가중치 간선을 선택해나간다는 점에서 비슷하지만.

다익스트라 알고리즘은 항상 시작정점을 기준으로 가중치를 계산하기에 5의 가중치를 가진 위의 정점을 가기 위해

15 + 5 = 20. 이라고 계산하지만. (나중에 더 좋은 가중치의 합을 구하면 교체)

 

프림 알고리즘은 트리의 집합으로. 1번과 2번이 이어졌다면(15) 그것을 기준으로 가중치 5라는 간선을 바라본다.

 

밑은 참고. 우선순위 큐에서 정렬을 할 때, 연산자 오버로딩 <는 const(매개변수),const(const 멤버 함수)를 해줘야함.

struct CostEdge
	{
		int cost;
		Pos vertex;

		bool operator<(const CostEdge& other) const
		{
			return cost < other.cost;

		}
	};