[Algorithms] Minimum spanning tree 알고리즘
우선 Spanning tree의 정의에 대해서 되돌아볼 필요가 있다. 스패닝 트리는 어떠한 그래프의 서브그래프이면서 그래프의 모든 버텍스를 포함하는 트리이다. 그러한 그래프가 edge에 weight를 가질때, weight의 합을 최소화하는 스패닝 트리를 Minimum spanning tree라 하며 그것을 구하는 알고리즘으로 Prim's algorithm과 Kruskal's algorithm이 있다. 위 두가지 방법은 Greedy Approach를 이용하여서 각자의 기준을 가지고 스패닝 트리를 만들게 된다. 우선 첫째로, Prim의 알고리즘은 하나의 버텍스에서 시작하여 인접한 버텍스 중 가장 웨이트가 작은 엣지로 연결된 버텍스를 선택하고 연결한다. 여기에서 인접한 버텍스 중 가장 웨이트가 작은 엣지로 연..
Computer Science
2011. 7. 7. 19:39
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- Data Structure
- 기계학습
- 리버싱
- reversing
- operating systems
- 자바
- 개발
- 카타르 음주
- 운영체제
- 카타르
- 알고리즘
- 데이터 사이언스
- 이산수학
- Data Science
- 데이터 과학
- Algorithms
- 통계학습
- Machine Learning
- 대학원
- android
- Discrete Mathematics
- 자료구조
- 머신러닝
- statistical learning
- 안드로이드
- 리눅스
- linux
- Reverse Engineering
- 리버스엔지니어링
- java
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함