최소 신장 트리

신장 트리 (Spanning Tree)

신장 트리는 다음과 같은 특징을 가진다.

1. 그래프의 모든 정점을 포함한다
2. 최소한의 간선의 개수를 가진다 ( 즉, 정점의 개수 - 1 개의 간선을 가진다)
3. 트리이기에 사이클을 가지지 않는다

 

위와같은 그래프가 있다고 할때 다음과같이 여러개의 신장 트리들이 나올 수 있다. 

 

위의 예시 외에도 더 다양한 형태의 신장 트리가 존재한다.

최소 신장 트리 (Minimum Spanning Tree)

최소 신장 트리의 개념은 간단하다. 그래프의 존재하는 신장 트리중 가중치의 합이 가작 작은 신장 트리가 최소 신장 트리이다.

위의 예시에서는 왼쪽부터 차례대로 가중치의 합이 12, 16, 18 이다. 그 외에도 존재하는 신장 트리중 가장 작은 가중치의 합을 가진 최소 신장 트리는 아래의 트리이다. 가중치 12를 가진 트리이다

최소 신장 트리

 

최소 신장 트리를 구하는 알고리즘 

최소 신장 트리를 구하는 대표적인 알고리즘은 다음과같다. 예시와 구현 코드를 통해 알아보자.

1. 크루스칼 알고리즘

2024.08.13 - [알고리즘] - 크루스칼 알고리즘

크루스칼 알고리즘

 

2. 프림 알고리즘 

2024.08.14 - [알고리즘] - 프림 알고리즘

프림 알고리즘