최소 신장트리

1 개요

minimum spanning tree; MST, minimum weight spanning tree, minimum cost spanning tree

최소 스패닝 트리, 최소 신장트리, 최소가중신장트리, 최소비용신장트리

• 한 그래프의 신장트리들 중에서 가중치 합이 가장 작은 것
• 활용예시: 통신망 구축시 전화선 길이 최소화, 건축시 파이프 길이 최소화

 

2 같이 보기

• Kruskal의 알고리즘
• 신장트리
• 가중치

3 참고

• https://en.wikipedia.org/wiki/Minimum_spanning_tree
• http://terms.naver.com/entry.nhn?docId=829519&cid=50376&categoryId=50376
• http://navercast.naver.com/contents.nhn?rid=2871&contents_id=86840
• http://news.chosun.com/site/data/html_dir/2015/04/12/2015041200320.html