9급 공무원/컴퓨터 일반
[자료구조] 신장트리(Spanning Tree)
리안아범
2017. 3. 5. 20:15
: 그래프에서 모든 정점을 연결하는 최소의 경로가 있을 때, 이것을 신장트리라 한다.
> 정점이 n개 일 때 신장트리의 간선의 개수는 n-1 (n개의 정점을 연결해야 하니까)
> 사이클이 있으면 안된다. 그럼 최소의 경로가 아니니까
**(중요) 배 속에 있는 신장과 무관하다
EX)
[이미지 펌 : https://t1.daumcdn.net/cfile/tistory/2769543652D9233431 // http://emzei.tistory.com/126 ]