Spanning Tree (신장 트리) 란?
Spanning Tree (신장 트리)란 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리이다.
무방향 그래프란 방향성이 없는 그래프로 그림상에서 화살표가 아닌 실선으로 이루어진 그래프를 뜻한다.
즉, Spanning Tree는 최소의 간선을 이용하여 모든 정점을 연결한 그래프이다.
너비 우선 탐색을 이용하여 생성된 신장 트리를 BFS (Breath First Spanning tree, 너비 우선 신장 트리)라고 하고,
깊이 우선 탐색을 이용해 생성된 신장 트리를 DFS (Depth First Spanning tree, 깊이 우선 신장 트리)라고 한다.
Spanning tree는 최소의 도로를 이용한 도로망 건설이나 최소의 네트워크선을 이용한 통신망 설계 등에 응용이 되는 개념이다.
그래프(graph) 자료구조의 용어 정리
여기서 등장하는 그래프(graph) 자료구조의 용어를 간단히 정리해보자면,
그래프는 노드(Node)와 간선(Edge)으로 표현되는데 노드는 정점(Vertex)이라고도 불린다.
앞서 예시로 든 도로망 건설을 예로 들면, 도시는 노드, 도로는 간선으로 비유할 수 있다.
정리하자면 아래와 같다.
1) 노드(Node) = 정점(Vertex) = V = 도시 = 그래프에서 동그라미로 표현
2) 간선(Edge) = E = 도로 = 거리 = 비용 = 그래프에서 선으로 표현
Minimum Spanning Tree (최소 신장 트리) 란?
영어로는 Minimum Spanning Tree라고 하며 약자로는 MST로 불린다.
MST는 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것을 말한다.
MST는 다음과 같은 조건을 가진다.
1) 간선의 가중치의 합이 최소여야 한다.
2) n개의 정점을 가지는 그래프에 대해 반드시 (n-1) 개의 간선만을 사용해야 한다.
3) 사이클이 포함되어서는 안 된다.
다음 예시를 살펴보면 이해가 쉬울 것이다.
- 그림(a)의 그래프가 있을 때 ,
- 그림(b)은 Spanning Tree가 아니다. 노드 v3, v4, v5가 사이클을 이루기 때문이다.
- 그림(c)은 Spanning Tree이지만 Minimum Spanning Tree는 아니다.
- 그림(d)은 Spanning Tree이며 Minimum Spanning Tree이다. (weight의 합이 10으로 가장 작기 때문)
Minimum Spanning Tree는 Unique 하게 1개만 나오지는 않고 여러 개가 나올 수 있다.
예를 들어 그림(d)에서 v1과 v3대신, v2와 v3를 연결해도 MST이다. (weight가 3으로 동일)
또한 vertex(정점)가 5개이므로 edge(간선)이 4개인 사실도 함께 확인해볼 수 있다.
그렇다면 Spanning Tree가 주어졌을 때, MST는 어떻게 계산할 수 있을까?
대표적으로 Kruskal 알고리즘과 Prim 알고리즘으로 구현할 수 있다.
이 두 가지 알고리즘 모두 Greedy Algorithm (탐욕 알고리즘)으로 설계가 되었다.
그리디 알고리즘으로 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것이다.
Kruskal과 Prim 알고리즘 두 가지가 이름이 헷갈리는데.. 착각하지 않도록 잘 기억해 두자.
(알고리즘 시험(?)에서 자주 등장하는 내용이다.)
Union-Find를 응용한 MST 알고리즘이 Kruskal임을 잘 기억해두자!!
Kruskal's Algorithm (크러스컬 알고리즘)
아래의 두 조건을 기반으로 간선을 선택하게 되며 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이다.
Kruskal 알고리즘은 여러 나무가 있는 숲에서 작은 나무들끼리 연결을 해가며 큰 나무 하나를 만드는 느낌이 든다.
1) 최소 비용의 간선으로 구성되어야 한다.
2) 사이클을 포함하지 않아야 한다.
이때 사이클이 발생하는지 아닌지의 여부는 Union-Find 알고리즘을 적용하면 된다.
Kruskal 알고리즘의 조금 더 상세한 플로우는 아래에 정리해 두었다.
Flow
1) 그래프의 간선들을 가중치를 기준으로 오름차순 정렬한다.
2) 정렬된 간선 리스트에서 순서대로 낮은 가중치를 먼저 선택한다.
3) 단, 이때 사이클을 형성하는 간선은 제외해야 한다.
4) 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다.
Prim's Algorithm (프림 알고리즘)
시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방식이다.
이때, 기존 정점도 포함시키면서 기존 정점에서 포함시키는 모든 간선들을 비교해나가는 방법이다.
Prim 알고리즘은 Kruskal과 달리 하나의 정점에서 시작해서 Tree가 점점 확장하게 되는데, 한 그루의 나무가 씨앗 하나부터 시작해서 점점 자라나는 느낌이 든다.
플로우는 아래와 같다.
Flow
1) 먼저 임의의 정점(시작 정점)을 선택하여 MST 집합에 포함시킨다.
2) 앞 단계에서 만들어진 MST 집합들에 인접한 정점들 중에서 최소 간선(가장 낮은 가중치)으로 연결된 정점을 선택하여 트리를 확장한다.
3) 위의 과정을 트리가 (N-1) 개의 간선을 가질 때까지 반복한다.
그래프 G(V, E)에서, 이진힙을 이용하면 평균 O(E*logV)의 시간 복잡도를 가지며, 최악의 경우 O(V^2)의 시간 복잡도를 가진다.
아래에 예시 자료를 첨부했다.
'프로그래밍 > 알고리즘 스터디' 카테고리의 다른 글
| [알고리즘] 회의실 배정 문제의 여러가지 풀이법 (Brute-Force, 분할정복, DP, 그리디) (0) | 2022.12.04 |
|---|---|
| [알고리즘] Stable sorting algorithm, In-Place algorithm (0) | 2022.10.24 |
| 정렬 알고리즘 총정리 (0) | 2022.10.24 |
