리안이와 함께하는 세상

[자료구조] 신장트리(Spanning Tree) 본문

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 ]

저작자표시 비영리 변경금지

'9급 공무원 > 컴퓨터 일반' 카테고리의 다른 글

[자료구조] 위상정렬  (0) 2017.03.05
[자료구조] 최소비용 신장트리(MST, Minimum cost Spanning Tree)  (0) 2017.03.05
[자료구조] 트리의 내부경로길이  (0) 2017.03.05
[자료구조] 데크(DeQueue)  (0) 2017.03.05
[자료구조] 스택 동적 배열  (0) 2017.03.05
'9급 공무원/컴퓨터 일반' Related Articles more