mir.pe (일반/밝은 화면)
최근 수정 시각 : 2022-08-04 01:42:29

생성나무

이 문서는 토막글입니다.

토막글 규정을 유의하시기 바랍니다.


Spanning Tree

생성 트리, 신장 트리라고도 한다. 사실상 다 같은 개념을 지칭하는 말이다.

그래프에서 모든 꼭지점(노드)를 포함하는 트리이다. 한 그래프는 여러 생성 나무를 가질 수 있지만, 반드시 모두 연결되어 있어야 하며, 연결되어 있지 않다면 생성 숲(Spanning Forest)이 되어 버린다.

네트워크, 통신망, 관계 시설 등을 계산하는 데 매우 유용한 개념이다. 최소 비용으로 통신망을 잇는 문제를 푸는 데 쓰이거나 한다. 이 중에서 특히 최솟값을 가지는 최소 비용 생성 나무는 영어로 Minimum Spanning Tree라고 하며, 크러스컬 알고리즘이나 프림 알고리즘으로 찾을 수 있다.

사실 다익스트라 알고리즘도 뜯어보면 내부적으로 생성나무를 일단 만들어서 쓴다.

분류