[자료구조] 신장트리(Spanning Tree) & 최소 신장 트리(MST)

[자료구조] 신장트리(Spanning Tree) & 최소 신장 트리(MST)

반응형

1. 신장 트리(Spanning Tree)란...?

Original 그래프에서 다음의 조건들을 만족시키는 그래프 -> (모든 노드가 연결 / 트리의 속성 만족(사이클 X))

신장 트리 조건

사이클 X Original 그래프의 모든 노드 포함 모든 노드 연결

1번째가 Original 그래프 / 2,3,4번째는 신장 트리

2. 최소 신장 트리(MST)란...?

Minimum Spanning Tree

신장 트리 중에서, 간선의 가중치 합이 최소인 것

토목, 통신 등등 다양한 분야에서 활용 가능

반응형

from http://tipsyziasu.tistory.com/121 by ccl(A) rewrite - 2021-08-21 19:26:22