스패닝 트리(Spanning Tree), 최소비용신장트리(MST), 프림(Prim) 알고리즘

MST와 Prim 알고리즘에 대해 공부해 보자.

목차는 다음과 같다.

Spanning Tree란?

MST란?

Prim알고리즘

Prim알고리즘 실전 문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

그럼 이제 Spanning Tree에 대해 알아보자.

Spanning Tree란? 모든 정점(노드)을 포함하면서 간선의 개수가 최소인 트리를 말한다.

특징은 다음과 같다.

앞서 말한 듯 모든 정점을 포함하면서 간선의 개수가 최소다.

사이클이 없는 그래프다.(사이클이 없는 그래프를 트리라고 말한다.)

그럼 위 2가지 특징을 통해 알 수 있는 사실이 있다.

Spanning Tree는 모든 정점을 포함하면서 간선의 개수가 최소이려면 간선의 개수는 정점 - 1이 될 수밖에 없다.

이와 관련되어 좀 더 자세히 알아보자.

위와 같이 그래프가 존재할 때 Spanning Tree가 되기 위하여 연결된 간선들을 지워보자.

우선 정점의 개수가 5개라면 간선의 개수는 4개가 되어야 한다.

위 특징을 만족하도록 연결된 간선들만 나타내면

다음과 같이 나타낼 수 있다.(예시로 나타낸 그래프와 다르게 나오는 Spanning Tree 또한 존재한다.)

 

 

그럼 다음으로 MST(Minimum Spanning Tree)에 대해 알아보자.

쉽게 말하면 앞서 공부한 Spanning Tree에 최소 비용을 만족하는 트리를 말한다.

그럼 최소 비용을 어떻게 만족할까를 잠깐 생각해보자.

연결된 간선의 가중치 값들의 합이 최소 비용이면 MST를 만족한다.