그래프 - Prim식 최소신장트리??

안녕하세요~ 테슬라 입니다.

저번에 이어서 이번 포스트는 최소신장트리 구현방식중에 하나인
Prim식 최소신장트리에 대해서 알아보도록 합시다.


저번 포스팅때 했던 Kruskal식을 생각해보죠...

그냥 가중치가 작은 순서대로 간선들을 이어서 하나의 최소신장트리를 만들었죠?

하지만 그 방법은 생각해보면 여러개의 트리를 잇고 이어서 하나의 큰 트리를 만드는 것이라고 생각할 수 있습니다. 예를 들어볼까요?

이런 그래프가 있다고 하죠. Kruskal식의 경우

라면,

이런 방법이지요?

이때 보시는 것처럼 여러개의 트리가 생긴 뒤 마지막에 모두 이어지는 모습을 보실 수 있으실거에요.

그런데 Prim식은 그런식으로 나눠져있다가 연결되는 방식을 거부한다는 것이지요.

말인즉슨, 하나의 트리에 계속 하나하나 간선들을 추가해서 이어나가는 겁니다.

단! 이때에도 역시 가중치가 작은 순서대로 잇는것입니다. 그래야 최소신장트리가 되는것이지요.

아까의 그림으로 연결해볼까요?

이런식인 것이죠. 자 첫번째는 시작이지요. 아까 Kruskal식의 두번째와는 다르게도 (1,2)와 연결하지요?

이는 1번에 연결되어있는 정점 ①과 ②로 구성된 트리에 연결할 수 있는 간선들 중 가중치가 제일 적은 것을 연결하는 것이지요.

세번째에서도 이처럼 정점 ①과 ②, ③으로 구성된 트리에서 연결할 수 있는 간선들 중 가장 가중치가 적은 (1,4)를 연결한 것입니다.

네번째도 결국 이어서 이런 모양이 되는 것이지요.

이런 식으로 별도의 트리를 만들어지지 않고 최소신장트리를 만드는 방법이 Prim식인 것이지요.


오늘은 여기까지입니다.
오늘도 혹시나 틀린 부분이나 오타 부분이 있다면 지적해 주시면 감사할 것입니다. 후훗