2024. 3. 29. 20:59ㆍ크래프톤 정글 5기/공부
Minimum Spanning Tree는 최소 신장 트리이다.
Spanning 이 무슨 뜻인지가 잘 와닿지 않았는데, 그래프에 존재하는 '모든 (Vertex=Node=)정점'을 탐색한 트리이다.
Tree, Graph, Forest와 같은 다른 개념들이 선행되어야 이해하기 편하기 때문에 차근차근 내가 이해한 걸 작성해보겠다.
[Tree]
Graph는 Directed/Undirected, Cyclic/Acyclic 구분 없이 Vertex와 Edge로 구성된 하나의 집합체를 의미한다.
Tree는 Graph의 하위 개념으로, Undirected + Acyclic 구조를 가진 그래프를 말한다.
1. Vertex마다 개별적인 Edge로 연결되어 있고 (Acyclic)
2. Edge에 특정 방향으로만 가게 하는 방향성이 존재하지 않는다. (Undirected)
*Tree는 1개의 그래프에 1개 이상 존재할 수 있다.
이미지는 밑에 작성할 Spanning Tree에 대한 내용이지만, 맨 위에 표현된 '하나의 그래프' 안에 여러 개의 트리가 존재하는 걸 확인했다.
여기까지 그래프와 트리에 대해 이해하며, 트리를 '탐색할 가능성이 존재하는 경로'로 이해했다.
또한 'Undirected, Acyclic' 조건을 충족하는 Tree는
{Vertex 개수 - Edge 개수 = 1 } 공식을 항상 만족한다.
Tree에서 기억해야하는 개념은 [Undirected, Acyclic] 이라고 생각한다.
[Forest]
Forest는 'Disjoint union of trees' -> 트리 구조이지만, 서로 연결되어 있지 않는 트리의 집합으로 이해했다.
이 이미지에서는 2개의 트리는 연결되어있지 않으며 나란히 존재한다.
왼쪽과 오른쪽 모두 트리의 조건 (Undirected, Acyclic)을 충족하고 있으며 개별적인 트리로 존재한다.
하지만 두 트리는 서로 연결되어있지 않기에, Forest라고 불러도 된다고 이해했다.
위에서 Tree는 {Vertex 개수 - Edge 개수 = 1} 를 만족한다고 했다.
Forest 안에 존재하는 {Vertex 개수 - Edge 개수 = Tree의 개수} 공식 또한 만족하는 걸 확인할 수 있다.
이로 인해 Forest 안에 존재하는 {Vertex 개수 - Edge 개수} > 1 일 경우, Forest라고 할 수 있겠다.
이 이미지는 Tree, Forest 둘 다 아닌 그저 하나의 Graph이다.
Tree의 조건인 Acyclic을 충족하지 못했고, 모든 Vertex가 Edge로 연결되어 있기 때문이다.
[Spanning Tree]
다시 Tree로 돌아와서, 몇 가지의 조건을 충족하면 Spanning Tree라고 부를 수 있게 된다.
기존의 Tree에 대한 조건을 충족한 채로, Graph에 존재하는 모든 Vertex를 포함하여 지나간다면 Spanning Tree가 된다.
다시 위에 있던 이미지를 보게 된다면, 그래프에 존재하는 4개의 Vertex를 모두 포함한 Tree가 곧 Spanning Tree임을 알 수 있다.
Spanning Tree에는 몇개의 특성이 존재한다.
[1] 연결되지 않은 그래프에는 / Spanning Tree가 존재하지 않는다.
여기서 연결되지 않은 그래프 --> Forest로 이해했다.
위에 있던 Forest의 이미지를 다시 본다.
2개의 Tree가 서로 연결되어 있지 않다. 이는 곧 모든 Vertex를 지나가는 Tree가 존재하지 못한다는 뜻이다.
그렇다면 '모든 Vertex를 지나가는 Forest' 라는건 존재할까 ?
[Spanning Forest]
초록색으로 표시된 트리를 본다면, 연결되어 있지 않은 2개의 트리임을 알 수 있다.
이에 더하여 연결되어있지는 않지만, 2개의 트리가 그래프 안에 있는 모든 Vertex를 지나고 있다.
이런 형태의 Graph는 Spanning Forest라고 불러도 무방하다.
[2] Graph에서 Spanning Tree가 존재한다면, Spanning Tree의 Edge 개수 = Vertex 개수 - 1 이다.
이 공식에서 -1과 Edge 개수를 옆으로 이동시키면, 앞의 Tree에서 봤던 {Vertex 개수 - Edge 개수 = 1}과 똑같게 된다.
[3] Spanning Tree는 Acyclic한 성질을 띄운다.
이는 당연한 말이라고 생각한다. Spanning Tree는 'Tree의 기본 조건 충족 + 모든 Vertex 지남' 이라는 조건이기 때문이다.
[4] Cyclic, Undirected 성질을 띄우는 Graph에서 Spanning Tree를 구성하려면, (Edge - Vertex + 1) 개의 Edge를 제거하면 된다.
[5] Cayley's Formula : Spanning Tree의 개수를 구하는 공식
이 그래프는 Cyclic, Undirected 한 상태이다. 여기서 (Edge - Vertex + 1) = 3개의 Edge를 제거하면 Spanning Tree가 된다.
Cayley's Formula를 사용하여 Spanning Tree의 개수를 구하려면, V**(V-2) 계산을 통해 구할 수 있다.
[MST, Minimum Spanning Tree]
지금까지 Minimum Spanning Tree를 알기 위해 Spanning Tree를,
Spanning Tree를 알기 위해 Tree를,
Tree를 알기 위해 Graph를, 그러면서 Forest를 알게 되었다.
MST를 한글로 최소신장트리 라고 하는데, 나는 '가중치가 최소인 Spanning Tree 탐색' 으로 이해했다.
지금까지 는 Edge에 가중치라는 요소가 표현되지 않았으나, 만약 Edge에 특정 가중치가 존재한다면 최소값을 구할 일이 있을 것이다.
네비게이션에 경로를 검색하면, 어떤 경로로 가는 것이 가장 도로 이용 비용이 저렴한가와 같은 선택지가 존재하지 않는가 ?
왼쪽과 같은 그래프에서, MST는 1, 2, 3 Vertex를 지나는 경로가 채택될 것이다.
Minimum Spanning Tree에도 특성이 존재한다.
[1] MST는 모든 Vertex를 연결한다.
Spanning Tree의 조건이므로 당연한 말이다.
[2] MST는 Acyclic 하다.
Tree의 존재 조건이므로 당연한 말이다.
[3] MST는 V개의 Vertex와 V-1개의 Edge를 가진다.
Tree와 Spanning Tree 모두 해당 공식을 만족하니, 당연한 말이다.
[4] MST는 그래프에서 유일하지 않다.
Tree도, Spanning Tree도 그래프에서 유일하지 않을 수 있다.
가중치가 존재하는 Edge가 있더라도, 동일한 가중치를 가지는 1개 이상의 Spanning Tree가 존재할 것이다.
[Algorithms to Find Minimum Spanning Tree]
Minimum Spanning Tree를 구현하는 알고리즘에는 크게 두가지가 있다.
1) Kruskal's MST Algorithm
우선 Kruskal 알고리즘은 Greedy Algorithm을 기반으로 한다.
Greedy Algorithm은 간단하게 '선택의 순간마다 최적의 상황만을 선택하는 것' 으로 이해했다. 이러한 방법으로 우리가 원하는 값을 찾기 위해서는, 최대한 선택의 순간마다 전체적으로도 최적의 값에 가까워지게 유도하는 과정이 필요할 것이다.
최대한 간단하게 Kruskal 알고리즘의 동작과정을 써보겠다.
1. 그래프에 존재하는 모든 Edge의 가중치를 오름차순으로 정렬한다.
2. 정렬된 요소를 첫 번째부터 선택하면서, '해당 경로를 선택하면 Cyclic 성질을 띄우게 되는지' 판단하며, 아니라면 선택한다.
빨간색 라인은 선택할 시 Cyclic 성질을 띄우게 되니, 선택할 수 없는 Edge를 나타낸 것이다.
이렇게 선택할 수 없는 Edge를 피해가며 모든 Vertex를 지나가게 되면, 1개의 Minimum Spanning Tree를 얻을 수 있다.
가중치를 오름차순으로 정렬하여 선택하는 건 이해했다. 그럼 Acyclic 성질 유지를 위해 Edge를 배제하는 건 어떻게 하는건가?
1-2) Union-Find Algorithm
Union-Find 알고리즘은 [Set - Union - Find] 순서대로 값을 찾아내는 동작으로 이해했다.
1. Set
처음 주어진 그래프의 모든 Vertex의 연결성을 무시하고, 각기 다른 번호로 배열화한다.
2. Union
우리에게 주어진 그래프의 연결성을 참고하여, 배열 값을 변경해 연결성을 추가해준다.
이를 트리 구조로 만들게 된다면
이런 연결성을 가진 그래프가 될 것이다.
3. Find
이제 배열로 부모-자식 관계를 확인할 수 있으니, 조건문을 활용하여 값을 비교하면
해당 경로를 선택해도 Acyclic 성질이 깨지지 않는 지 확인할 수 있을 것이다.
이러한 'Acyclic 성질을 유지하기 위한 Edge 선택 알고리즘'인 Union-Find 알고리즘은, 만약 선형적인 연결성을 가진 그래프가 주어질 경우 연산이 비효율적일 수 있을 것이다.
이를 해결하기 위해 Path Compression, Union by rank와 같은 알고리즘 강화법이 존재한다고 한다.
저 두가지 강화법을 이해한 바로는, 어차피 Union-Find Algorithm은 '각 Vertex 마다의 연결성'만 확인하면 되므로, 최대한 불필요한 연산을 줄이려는 개선방법이였다.
이러한 알고리즘 강화법은 추후 내가 백준에서 문제를 풀 때 적용해 본다면 다시 작성할 예정이다.
2) Prim MST Algorithm
Kruskal MST Algorithm은 간단하게
'Edge 별 가중치를 오름차순으로 정렬 → 최소 가중치 간선 선택 → 선택 불가능한 edge 배제해가며 → tree 완성'으로 이해했다.
Prim 알고리즘도 비슷하다고 생각했지만, 탐색 접근 방법이 다르다고 이해했다.
Prim MST는 무조건 함수 입력에 ‘시작 Vertex’ 를 지정해줘야 한다. 0번 vertex를 선택한다면 ?
현재 0, 1번 Vertex를 선택했다. 이제 비교해야 하는 Edge는, 이전 단계에서 고르지 않은 0→7 Edge도 포함하여 비교한다.
—> 0→7, 1→2, 1→7 Edge 가중치를 비교하여 최소가중치인 Edge로 이동하는 것이다.
이러한 과정을 (V-1) 개의 Edge가 선택될 때까지 반복한다.
탐색이 종료되면, 위와 같은 1개의 MTS를 얻을 수 있다. 이를 반복하게 되면, 모든 MTS를 얻을 수 있을 것이다.
[Kruskal’s MST Algorithm VS Prim MST Algorithm]
- 간선(Edge)의 개수가 중요하다.
- 간선의 개수가 적다면, 선택 가능한 간선을 모두 선택하는 과정의 Kruskal 기법이 더 효율적이다.
- 간선의 개수가 많다면, 1개의 간선만을 선택해가며 탐색을 진행해가는 Prim 기법이 더 효율적이다.
내가 이해한 것이 모두 맞는지는 모르겠지만, 공부를 통해 각 단계별 특성을 이해하고 동작 과정 또한 끄덕거리며 볼 수 있었다.
이를 코드로 구현하는건 나에게 어려운 도전이겠지만, 열심히 백준 문제 풀이를 통해 개념을 코드화 해봐야겠다.
'크래프톤 정글 5기 > 공부' 카테고리의 다른 글
| Malloc Lab (0) | 2024.04.28 |
|---|---|
| 분할정복, Divde / Conquer / Combine (0) | 2024.04.06 |
| B-Tree, Balanced Tree (1) | 2024.04.06 |
| DFS, Depth First Search (0) | 2024.03.28 |
| SSR, CSR 동작원리와 장단점 (0) | 2024.03.25 |