[알고리즘] 최소비용신장트리(Minimum Spanning Tree) - 4

최소비용신장트리(Minimum Spanning Tree) - 4

이번에는 두번째 MST인 프림의 알고리즘에 대해 알아보자

프림의 알고리즘도 마찬가지로 안전한 엣지를 하나씩 추가함으로 완성되는데

안전한 엣지를 찾는 방법이 크루스칼의 알고리즘과 다르다.

프림의 알고리즘에서는 먼저 출발점인 노드를 선택해야한다.

그리고 그 출발점인 노드에서부터 점점 몸집을 키우기 시작한다.

즉, 출발 노드에서 인접한 노드를 선택하고, 여기서 나가는 엣지를 하나 선택하고, 이를 반복한다.

크루스칼에서는 떨어진 노드들을 선택했는데 프림의 알고리즘은 인접한 노드를 선택하는것이 차이점이다.

이 때, 어떤 엣지를 선택하느냐에 대한 방법을 알아봐야하는데,

매 단계에서 트리에 포함되어진 노드와 포함되지 않은 노드 사이에 가중치가 가장 작은 엣지를 선택한다.

먼저 출발 노드를 선택하는데 아무 노드나 선택하면 된다.

위의 그림에서는 노드 a를 선택했다.

a와 인접한 노드는 b 와 h가 있는데, 둘 중에 b와 연결된 엣지의 가중치가 낮으므로 b와 연결해준다.

같은 원리로 c와 h중에 c와 연결된 엣지의 가중치가 낮으므로 c와 연결해준다.

동일한 방법으로 노드 i와도 연결된다.

이를 반복해서 결국 엣지가 n-1일때까지 반복을 하면 MST가 완성된다.

위의 코드는 프림의 알고리즘에 대한 슈도 코드이다.

우선 출발점을 0으로 설정해주고 while문으로 엣지가 n-1일때까지 반복한다.

그리고 while문안에서 최소값을 찾아 Va에 포함시키고 

u에 인접하면서 Va에 속하지 않은 각각의 값에 대해 key값을 갱신한다.

이 때 while 문은 n-1번 반복되며, for 문에 의해 키값이 갱신되므로

시간복잡도는 O(n^2)으로 표현된다.

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘