[Algorithm] 최소 신장 트리(MST, Minimum Spanning Tree)

개요

 

◎ 최소 신장 트리란?

◎ 신장 트리란?

◎ 그림 예시

◎ 신장 트리 특징

◎ 최소 신장 트리 구현 알고리즘

 

 

 

안녕하세요. J4J입니다.

 

이번 포스팅은 최소 신장 트리에 대해 적어보는 시간을 가져보려고 합니다.

 

 

최소 신장 트리란?

 

최소 신장 트리는 신장 트리들 중 가중치의 합이 가장 작은 신장 트리를 의미합니다.

 

여기서 가중치라고 하는 것은 그래프에서 길(간선)을 지나기 위해 지불되는 값이라고 생각하면 됩니다.

 

예를 들어 A에서 출발하여 C에 도착한다고 가정해 보겠습니다.

 

A→B 가중치: 5

B→C 가중치: 8 이면

A→C로 이동하기 위한 가중치의 합은 13이 되는 것입니다.

 

 

신장 트리란?

 

신장 트리란 최소한의 길(간선)을 이용하여 모든 정점들을 이동 가능하도록 만들어진 트리입니다.

 

따라서 하나의 그래프에 대해 만들어질 수 있는 신장 트리는 한 가지만 존재하는 것이 아니라 두 개 이상이 존재할 수 있습니다.

 

그리고 만들어질 수 있는 신장 트리 중 가중치의 합이 가장 작은 것은 최소 신장 트리가 되는 겁니다.

 

 

그림 예시

 

모든 길(간선)이 연결되어 있는 그래프를 완전 그래프(Complete graph)라고 합니다.

 

정점이 4개인 완전 그래프가 있다고 가정해보면 다음과 같은 신장 트리들이 만들어 질 수 있습니다.

 

 

 

신장 트리 특징

 

1. 정점의 개수가 n개가 있다고 할 때 길(간선)의 개수는 n-1개가 됩니다.

 

2. 지나온 길을 거치지 않고 출발 지점으로 되돌아오는 사이클이 존재하지 않음

 

3. 모든 정점이 서로 연결되어 있음

 

4. 길(간선)이 한 개 이상 추가되면 사이클이 존재

 

5. 길(간선)이 한 개 이상 삭제되면 연결되지 않는 정점이 존재

 

6. 완전 그래프에서 정점의 개수가 n개 일 때 신장 트리의 개수는 최대 n^(n-2)개 존재

 

 

최소 신장 트리 구현 알고리즘

 

1. 프림 알고리즘 (Prim Algorithm)

 

2. 크루스칼 알고리즘 (Kruskal Algorithm)

 

둘에 대한 내용은 다음 포스팅에 이어서 작성하도록 하겠습니다.

 

 

정리

 

● 최소 신장 트리란 신장 트리 중 가중치의 합이 최소인 신장 트리를 의미

● 신장 트리는 최소한의 길(간선)을 이용하여 모든 정점들이 이동가능한 트리를 의미

● 신장 트리는 사이클이 존재하지 않음

● 신장 트리는 모든 정점이 연결되어 있음

● 정점의 개수가 n개 일때 신장 트리 길(간선)의 개수는 n-1개

● 대표적인 구현 알고리즘은 프림, 크루스칼이 존재

 

이상으로 최소 신장 트리에 대해 간단하게 알아보는 시간이었습니다.

 

읽어주셔서 감사합니다.