그래프 - 최소비용신장트리

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다. 

신장트리 Spanning Tree 

그래프 내의 모든 정점을 포함하는 트리

 

단, 아래의 3가지 조건을 모두 만족해야 한다.

 

1. 모든 정점들이 연결되어 있어야 한다.
2. 사이클 cycle 을 포함하면 안된다.
3. 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결한다.

 

신장트리는

깊이우선 탐색 또는 너비우선 탐색을 하면서

사용된 간선만 모으면 만들 수 있다.

 

즉, 신장트리는 그래프의 최소 연결 부분 그래프가 된다.

 

이러한 신장트리는 통신망 네트워크 구축 등에 사용된다.

통신망, 도로망, 유통망 등은 간선에 가중치가 부여된 네트워크이다. 

 

이를 가장 적은 비용으로 구축하고자 하려면

모든 정점들을 가장 적은 수의 간선과 비용으로 연결해야 한다.

 

이것이 최소 비용 신장 트리 (MST: Minimum Spanning Tree) 이다. 

 

최소 비용 신장 트리 (MST: Minimum Spanning Tree)

신장 트리 중에서
사용된 간선들의 가중치 합이
최소인 신장 트리

 

최소 비용 신장 트리를 구하는 대표적인 방법은 다음과 같다.

 

• Kruskal 의 MST 알고리즘
• Prim의 MST 알고리즘

 

이 알고리즘들이 반드시 따르는 조건 3가지는 다음과 같다.

 

1. 간선의 가중치의 합이 최소이다.
2. 모든 정점 n개에 대해 (n-1)개의 간선만 이용한다.
3. 사이클을 포함하지 않는다.

 

Kruskal과 Prim의 알고리즘은 다음 글에서 자세히 살펴본다.