[알고리즘] 최소신장트리, MST, 크루스칼/프림 알고리즘
_Spanning Tree 정의 Spanning Tree(신장트리)는 아래의 속성을 만족하는 그래프를 말한다. 원래의 그래프의 모든 노드를 포함 모든 노드가 서로 연결되어 있음 트리의 속성을 만족 ( 사이클이 존재하지 않음) 즉, 그래프의 최소 연결 부분 그래프이다. 최소 연결 = 간선의 수가 가장 적다 N개의 노드를 가진 그래프 최소 간선의 수 : N-1 (N-1)개의 간선으로 == 최소 간선으로 연결되어 있으며 트리의 형태이면 Spanning Tree _Minimum Spanning Tree (MST) 가능한 Spanning Tree 중에서 간선의 가중치 합이 최소인 Spanning Tree 위 사진에서 첫 번째 그래프의 경우 2개의 MST를 가질 수 있다. 두번째, 세번째 트리가 모두 가중치의 합이..
algorithm & data structure
2020. 12. 11. 15:47
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 네트워크
- 백준
- LinearLayout
- 이진탐색트리
- frameLayout
- BOJ
- 안드로이드
- DATABASE
- RelativeLayout
- 퀵정렬
- listview
- C++
- debug
- layout
- 운영체제
- OS
- 백준알고리즘
- 스프링부트
- WinDbg
- 윈도우
- Android
- 정렬 알고리즘
- adapter
- windows
- 알고리즘
- C
- handshake
- ConstraintLayout
- 스프링
- HTTP
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함