C로 만드는 자료구조 - 신장 트리(Spanning Tree)와 최소비용신장트리

신장 트리(Spanning Tree)의 개념

 앞서 그래프에 대한 내용을 다루었다. 내용을 살펴보면 그래프 G는 노드 V와 간선 E의 집합으로 정의된다는 것을 알 수 있다. 다시 정리하자면 그래프는 노드와 노드들을 연결하는 간선들의 집합으로 구성되어있고 그래프의 정의를 식으로 나타내면 G=(V,G)이다. 

이번에 다룰 내용은 일반적인 그래프 G에 대한 신장 트리(Spanning Tree)에 관한 것이다.

 여기서 ‘신장(spanning)’은 모든 노드를 포함한다는 뜻이다. 만약 노드가 5개인 그래프 G에 대해 신장트리를 만든다고 한다면 신장트리는 반드시 저 5개 노드를 포함하고 있어야 한다. 하지만 신장 트리도 엄연히 트리의 일종이기 때문에 그래프와 다른 트리의 특징인 순환 구조를 가지면 안된다. 정리하자면 신장트리는 기존 그래프의 모든 노드를 포함하고 순환 구조없이 연결한 트리를 말한다. 따라서 신장 트리는 모든 노드가 연결되어져 있다면 부가적으로 그래프의 또다른 간선을 추가할 필요는 없다.

아래 그림은 그래프 G에 대한 모든 신장 트리의 예이다.

 위 예시를 보면 신장 트리의 간선 개수는 그래프의 간선 개수보다 적으며 정확히 말하면 모든 노드의 수를 N이라고 한다면 신장트리의 간선 개수는 N-1이 된다.

또한 그래프 G의 간선 중에서 신장 트리에도 포함된 간선을 트리 간선(Tree Edge)라고 하며 신장 트리에 포함되지 않은 간선을 비트리 간선(Non-tree Edge)라고 한다.

 신장 트리는 그래프의 개념으로 말하면 기존 그래프의 모든 노드를 포함하면서 순환 구조가 존재하지 않는 부분 그래프(Sub-graph)이다.

구체적인 식으로 나타내면 다음과 같다.

G’ = ( V(G’) , E(G’) )

V(G’) = V(G)

E(G’) ⊂ E(G)

 이러한 신장트리는 그래프 탐색을 이용하여 생성할 수 있다. 앞서 설명한 깊이/넒이 우선 탐색으로도 각각 깊이/넓이 우선 신장 트리를 구할 수 있다. 신장 트리를 실제 사용하는 것은 주로 최소 비용 신장트리 문제이다. 이제 최소 비용 신장 트리가 무엇이고 어떻게 만들어야 할지 알아보자.

최소 비용 신장 트리의 개념

 최소 비용 신장트리는 그래프 G가 가중치를 가질 때 그래프 G의 신장 트리들중 가중치들의 합이 가장 작은 신장트리를 말한다. 최소 비용 신장트리는 어떤 상황에서 사용할 수 있을까? 예를 들어 전국 모든 도시를 연결하는 인터넷 연결망을 설치를 해야하는데 이를 설계한다고 생각해보자. 이때 각 도시사이에 산이나 강, 거리에 따라 설치비용이 각각 다를 것이다. 이를 해결하기 위해서 우리는 비용이 가장 적게드는 최소 비용 신장트리가 필요하다.

아래는 최소 비용 신장트리의 예이다. 

 위 그림에서 신장 트리 3개중에서 (1)은 가중치의 합이 9이고 (2)는 7 (3)은 8이기 때문에 최소 신장트리는 (2)번 신장트리이다. 

 이러한 최소 비용 신장 트리를 만드는 방법은 여러가지 방법이 있는데 가장 대표적인 kruskal 알고리즘과 prim 알고리즘에 대해 다음 글에 다루어 보려고한다.