티스토리 뷰
_Spanning Tree 정의
Spanning Tree(신장트리)는 아래의 속성을 만족하는 그래프를 말한다.
- 원래의 그래프의 모든 노드를 포함
- 모든 노드가 서로 연결되어 있음
- 트리의 속성을 만족 ( 사이클이 존재하지 않음)
즉, 그래프의 최소 연결 부분 그래프이다.
- 최소 연결 = 간선의 수가 가장 적다
- N개의 노드를 가진 그래프
- 최소 간선의 수 : N-1
- (N-1)개의 간선으로 == 최소 간선으로 연결되어 있으며 트리의 형태이면 Spanning Tree
_Minimum Spanning Tree (MST)
가능한 Spanning Tree 중에서 간선의 가중치 합이 최소인 Spanning Tree
위 사진에서 첫 번째 그래프의 경우 2개의 MST를 가질 수 있다.
두번째, 세번째 트리가 모두 가중치의 합이 최소이기 때문에 최소신장트리의 조건을 만족한다.
_MST 구현방법
그래프에서 MST(최소 신장 트리)를 찾을 수 있는 알고리즘
- Kruskal's algorithm (크루스칼 알고리즘)
- Prim's algorithm (프림 알고리즘)
'algorithm & data structure' 카테고리의 다른 글
[알고리즘] 정렬알고리즘 _ 버블, 선택, 삽입, 병합, 셸 (0) | 2018.11.21 |
---|---|
[알고리즘] 힙정렬(Heap Sort) (0) | 2018.10.25 |
[알고리즘] 퀵정렬(Quick Sort) (0) | 2018.10.25 |
[자료구조] 트리, 이진트리, 이진탐색트리 (0) | 2018.10.24 |
[알고리즘] 레드블랙트리(red-black tree) - 특징, 삽입 (0) | 2018.06.29 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 이진탐색트리
- 정렬 알고리즘
- LinearLayout
- adapter
- 네트워크
- Android
- ConstraintLayout
- 퀵정렬
- RelativeLayout
- HTTP
- BOJ
- OS
- 안드로이드
- 윈도우
- handshake
- debug
- windows
- 운영체제
- 알고리즘
- 백준
- frameLayout
- 백준알고리즘
- listview
- layout
- DATABASE
- C
- 스프링
- WinDbg
- 스프링부트
- C++
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
글 보관함