Spanning Tree (스패닝 트리, 신장 트리)
spanning tree는 방향이 없는 연결 그래프의 하위 그래프이며 모든 vertex(정점)을 가능한 최소의 edge(가지)로 연결한 그래프를 의미한다.
위 사진은 spanning tree의 예시로 A,B,C,D 4개의 vertex들이 최소의 edge로 모두 연결한 모습을 볼 수 있다.
예시와 함께 보충 설명하자면, 어떤 마을에서 어떤 집에서 출발하더라도 모든 집에 갈 수 있도록 가능한 길을 최소로 설치하는 것을 의미한다.
위와 같이 일반적으로 spanning tree는 vertex가 n이라면, 이들을 연결하는 edge는 n-1이 된다.
Minimum Spanning Tree ( 최소 스패닝 트리, 최소 신장 트리 )
minimum spanning tree는 spanning tree의 각 edge의 weight의 합이 가능한 최소인 경우이다.
위 그래프의 minimum spanning tree를 구해보자.
먼저 2가지 조건이 있어야 할 것이다.
- spanning tree여야 한다.
- 각 weight의 합이 최소여야 한다.
그러면 일단 1번 조건을 충족하는 경우들을 알아보자.
먼저 1번 조건을 충족하는 경우는 위 4가지의 경우이다. n개의 vertex들을 n-1의 edge로 연결하였다.
그리고 2번 조건을 충족하는 경우는 각 edge의 weight를 연결하여 최소합을 갖는 spanning tree를 찾으면 된다.
해당 조건에 해당되는 경우는 weight sum이 7인 경우이고, 해당 spanning tree가 minimun spanning tree가 된다.
How to find minimum spanning tree
minimun spanning tree를 찾기 위해 다음 2가지 알고리즘이 사용된다.
1. Prim's Algorithm
2. Kruskal's Algorithm
출처)
https://www.programiz.com/dsa/spanning-tree-and-minimum-spanning-tree
https://www.youtube.com/watch?v=Yldkh0aOEcg
