스패닝 트리 모든 정점이 최소 모서리 수로 연결된 무방향 그래프의 하위 집합입니다.
모든 정점이 하나의 그래프에 연결되어 있으면 적어도 하나의 스패닝 트리가 존재합니다. 그래프에는 하나 이상의 스패닝 트리가 있을 수 있습니다.
최소 스패닝 트리
최소 스패닝 트리(MST) 모든 정점을 가능한 최소 총 간선 가중치로 연결하는 연결된 가중치 무방향 그래프의 간선 부분 집합입니다. MST를 유도하기 위해서는 Prim의 알고리즘이나 Kruskal의 알고리즘을 사용할 수 있습니다. 따라서 이 장에서는 Prim의 알고리즘에 대해 설명합니다.
우리가 논의한 바와 같이, 하나의 그래프는 하나 이상의 스패닝 트리를 가질 수 있습니다. n이 있는 경우 정점 수, 스패닝 트리는 n - 1이어야 합니다. 가장자리의 수. 이러한 맥락에서 그래프의 각 간선이 가중치와 연관되어 있고 하나 이상의 확장 트리가 있는 경우 그래프의 최소 확장 트리를 찾아야 합니다.
또한 중복 가중치 간선이 있는 경우 그래프에 여러 개의 최소 스패닝 트리가 있을 수 있습니다.
위의 그래프에서는 최소 스패닝 트리는 아니지만 스패닝 트리를 표시했습니다. 이 스패닝 트리의 비용은 (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) =38입니다.