[그래프] 최소 신장 트리 (minimum spanning tree)
이번에는 그래프의 최소 신장 트리(minimum spanning tree)를 알아보자. 최소 신장 트리가 무엇일까? 먼저 그래프는 익히 알고 있을 것이다. 그래프는 노드와 간선으로 구성된다. 지하철 노선도로 비유하자면 지하철 역이 노드이고 지하철 역과 역을 잇는 선이 간선이 될 것이다. 지하철 역처럼 노드는 무엇인가를 나타내기 위해 사용하고 간선은 노드와 노드의 관계를 나타낸다. (어느 역과 어느 역이 연결되어 있는지 등) 간선은 보통 비용을 포함하고 있다. 비용의 종류는 그래프의 용도에 따라 다양하게 결정된다. 거리가 될 수도 있고 금전적인 진짜 비용이 될 수도 있다. 여기서 노드들과 노드들을 제각기 잇는 간선이 있을 때 모든 노드들을 최소의 비용을 들여 연결한 그래프 모습을 최소 신장 트리라고 한다...
알고리즘/study
2019. 11. 29. 00:09
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- KMP
- 최단 경로
- 문자열 검색 알고리즘
- Kruskal
- quick sort
- divide & conquer
- red black tree
- Strassen algorithm
- 퀵 소트
- 레드블랙트리
- Prim
- 퀵소트
- strassen
- 플로이드
- Introduction to Algorithms
- Dijkstra
- Median of Two Sorted Arrays
- 최단 경로 알고리즘
- leetcode
- operating system concepts
- Shortest path
- minimum spanning tree
- heapsort
- 힙 소트
- 레드 블랙 트리
- 최소 신장 트리
- string searching algorithm
- Longest Palindromic Substring
- rabin karp
- boyer moore
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함