[Algorithm] MST (최소 신장 트리)

프림(Prim) MST(Minimum Spanning Tree 최소 신장 트리)

프림 알고리즘(Prim's algorithm)

가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용을 찾는 알고리즘이다. (greedy algorithm 임)

개요

프림 알고리즘은 아래의 순서대로 작동한다:

1. 그래프에서 임의의 하나의 정점을 선택한다.
2. 선택한 정점과 인접하는 정점들중 최소 비용의 간선이 존재하게되는 정점을 선택한다.
3. 1.2 과정을 반복 하여 모든 정점이 선택될까지 한다.

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

동작 예제

	어떤 점에서 시작하던 관계는 없습니다. 좌측 그래프에서는 임의의 시작점 D를 선택합니다.
	D지점에 연결된 모든 정점에 대해 거리가 최소가 되는 정점을 선택합니다.	D
	여기에서는 A지점이 됩니다. D-A지점은 서로 연결을 시키게 됩니다.	DA
	A,D 정점 각각 모든 정점들에 대해 최소 비용을 계산합니다.	DAF
	D-F:6 비용이 최소가 됩니다. F정점을 추가합니다.	DAF
	지금까지 연결된 정점(A,D,F) 모두에 대하여 연결된 남은 정점들을 모두 검색해서 비용이 최소가 되는 정점을 구합니다.	DAF
	A-B가 7로서 최소값으로 추가되었습니다.	DAFB
	지금까지 연결된 B가 연결되면서 D-B상의 연결 검토는 필요가 없습니다.(회색) 왜냐하면 tree를 확장해나가는 조건이 연결이 안된 정점에 대해서 진행하기 때문입니다. 여기에서 최소값 검토 지점은 분홍색을 대상으로 진행합니다.	DAFB
	B-E가 7로서 최소값으로 E정점이 추가되었습니다.	DAFBE
	E정점이 추가됨으로서 D-E,F-E는 검토대상에서 사라졌으며 E-C,G-E 가 검토 대상에 추가되었습니다. 최소값은 E-C:5가 되면서 C지점이 추가가 될 것입니다.	DAFBE
	A-B가 7로서 최소값으로 추가되었습니다.	DAFBEC
	E-G 는 최소값 9로 추가 되었습니다.	DAFBECG