1. 스패닝 트리 / 신장 트리 / 생성 나무 (Spanning Tree)
ㅇ 루프 순환이 없는 그래프
- 일종의 루프 순환(looping, 예: Bridge Loop)을 방지하게되는 트리
. 한 노드에서 다른 노드에 이르는 경로가 오직 하나 뿐인 토폴로지
※ [참고용어]
- 그래프 : 기하학적인 도형,구조,방정식,알고리즘의 설명,해석 등을 위한 시각적 표현 도구
- 트리 : 노드 및 가지로 형성되는 그래프의 특수한 경우를 일컬음
- 토폴로지 : 외형적인 연결 모양/구조를 의미
2. 스패닝 트리 구조 (Spanning Tree Structure)
ㅇ 최상의 정점(중심)을 루트 노드(root)로 하고,
- 모든 그룹 멤버들을 자손으로 갖는 트리구조
ㅇ 모든 노드들이 연결되면서 비순환(Acyclic,루프 순환이 없는)인,
- 무방향 그래프의 일종
ㅇ 임의 그래프로부터 만들 수 있는 신장 트리는 매우 다양할 수 있음
3. 최소 비용 신장 트리, 최소 신장 트리
(Minimum Cost Spanning Tree, Minimum Spanning Tree, MST)
ㅇ 신장 트리 내 모든 간선의 가중치 합이 최소
ㅇ 특징
- 모든 정점들의 연결에 끊임이 없어야 함
- (간선의 수 + 1) = (정점의 수)
4. 최소비용 신장트리 생성 알고리즘 (Minimum Spanning Tree)
ㅇ 연결선에 부여된 가중치 합이 최소가 되도록 신장트리를 작성하는 알고리즘
ㅇ (대표적인 例)
- 쿠르스칼 알고리즘 (Kruskal Algorithm)
. 루프를 만들지 않으면서도, 최소 가중치를 갖는 연결선을 하나씩 추가하며, 신장트리 작성
.. 가중치로 간선을 정렬한 후, 사이클이 형성되지 않도록 하며,
.. 간선을 하나씩 선택 또는 삭제하며 신장트리를 만들어감
. 순환을 피하며 단순히 그 시점에 최소 가중치를 갖는 연결선을 선택하며,
.. 연결선 단위로 신장 트리를 구축하는 탐욕 알고리즘 접근법
. 최초에는 연결선이 전혀 없는 n개 개별 정점,n개 개별 트리로부터 시작
.. n-1개 연결선을 더하고 나면 모든 트리가 합처져서 하나의 신장 트리가 됨
- 프림 알고리즘 (Prim Algorithm)
. 하나의 정점을 시작으로 트리를 점차 확장시켜가며 신장트리 그래프를 만들어감
.. 임의 정점부터 시작하며, 연결된 연결선 중 최소 가중치를 갖는 연결선을 추가하고,
.. 루프를 만들지 않으면서,
.. 점차 선택된 정점들에 부속된 연결선들 중 최소 가중치 연결선을 추가하며 신장트리 작성
※ [참고] ☞ 탐욕 알고리즘, 그래프 알고리즘, 스패닝 트리 프로토콜