[알고리즘 개념] 신장트리(spanning tree)
신장트리(spanning tree)
- 특징
-
모든 정점이 연결되어 있으면서 사이클이 없는 트리이다
-
그래프에 있는 n개의 정점을 n-1개의 간선으로 연결한다
-
하나의 그래프에는 많은 신장트리가 존재 가능하다
-
깊이 우선 탐색이나 너비 우선 탐색 도중 간선만 모으면 만들 수 있다
//깊이 우선탐색을 개조한 신장트리 간선 모으기 depth_search(v): v를 방문처리 for u in (v에 인접한 정점 == u): if (u가 방문되지 않았다면): (v,u)를 신장 트리 간선으로 표시; depth_search(u);
-
신장 트리는 통신 네트워크 구축에 많이 사용된다. 예를 들어 n개의 위치를 연결하는 통신 네트워크를 최소의 링크를 이용하여 구축할 경우 최소 링크수는 (n-1)이 된다. 따라서 신장트리를 구함으로 써 해결할 수 있다. 하지만 각 링크의 구축비용은 같지 않다. 따라서 단순히 가장 적은 링크를 사용하는 것이 아닌 간선에 붙어있는 비용까지 고려하여 최소 비용의 신장트리를 선택할 필요가 있다
-
최소신장트리(Minimum spanning tree MST)
- 특징
- 신장트리 중에서 사용된 간선들의 가중치 합이 최소인 신장트리를 말한다
- 최소신장트리를 구하는 방법은 Kruskal과 Prim 알고리즘이 있다
Author And Source
이 문제에 관하여([알고리즘 개념] 신장트리(spanning tree)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gandi0330/알고리즘-개념-신장트리spanning-tree저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)