신장트리(Spanning Tree)
최소신장트리를 알기전 신장트리(Spanning Tree)에 대해서 알아야하는데요. 신장트리는 원래 그래프의 모든 노드를 포함하면서 사이클이 없는 부분 그래프를 의미합니다.
그래프 G가 있다는 가정하에 신장트리는 G의 모든 노드를 포함하면서 간선의 수가 V - 1인 부분 그래프입니다. 여기서 V는 그래프 G의 노드의 수를 의미합니다.
즉, 신장트리는 원래 그래프의 노드들을 모두 연결하면서, 사이클이 없어야 합니다.
최소신장트리와 다르게 신장트리에는 가중치가 없는 제한이 없습니다. 따라서, 신장트리를 구성하는 간선의 수는 그래프의 종류나 구조에 따라 다양할 수 있습니다.
위에서 설명한 것과 같이 스패닝 트리의 가장자리는 그래프의 정점 수에서 1을 뺀 것과 같습니다. 따라서 스패닝 트리에는 4개의 모서리가 있습니다.
위의 그래프에서 생성될 수 있는 일부 스패닝 트리는 다음과 같습니다.
최소신장트리(Minimum Spanning Tree, MST)
그래프 이론에서 사용되는 개념으로 그래프는 노드들과 그들 사이의 간선들로 이루어진 자료 구조를 말합니다. 최소신장트리는 가중치(weight)를 갖는 무방향 그래프에서 모든 노드를 포함하면서 사이클이 없는 부분 그래프 중에서 전체 가중치 합이 최소인 트리를 의미합니다.
간단히 말해, 최소신장트리는 주어진 그래프의 모든 노드를 가장 적은 비용으로 연결하는 부분 그래프를 찾는 것입니다.
최소신장트리를 찾는 알고리즘으로는 주로 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 사용됩니다.
사용분야
최소신장트리는 클러스터 분석 민간 네트워크 계획, 컴퓨터 네트워크 라우팅 프로토콜 등 다양한 분야에서 활용됩니다. 또한 최소신장트리는 그래프 이론의 중요한 개념으로써, 알고리즘과 데이터 구조에 대한 이해를 높이는 데 도움이 됩니다.
