[ 알고리즘 개념 ] 최소신장트리 (Minimum Spanning Tree)

최소신장트리 (Minimum Spanning Tree)

 

1. 개념

▷ 신장트리란?

- 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

( 큰 틀에서 트리에 포함되는 조건이다. )

- 즉, 누락된 노드가 존재하거나 사이클이 존재하면 신장트리 조건 위배

- 아래 예시와 같이 한 그래프에 여러 신장트리가 존재할 수 있다.

 

신장트리 예

▷ 최소신장트리란?

- 최소한의 비용으로 구성되는 신장트리

예) N개의 도시가 있고, 이 도시 사이에 도로를 놓아 전체 도시가 연결되어야 하는데 이때, 최소 비용으로 연결

최소신장트리 예

위 그림에서 두번째 신장 트리는 총 비용(Cost)이 11이므로 최소 신장 트리가 아니다.

세번째 신장 트리의 비용이 7로 더 작으므로 최소 신장 트리는 세번째이다.

 

최소 신장 트리 알고리즘에는 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 있다.

이에 대한 자세한 내용은 관련글에 설명해두었다.

 

관련글

크루스칼 알고리즘

https://codingexplore.tistory.com/62

[ 알고리즘 개념 ] 크루스칼 알고리즘 (Kruskal Algorithm)

 

프림 알고리즘

https://codingexplore.tistory.com/63

[ 알고리즘 개념 ] 프림 알고리즘 (Prim Algorithm)