생성나무

이 문서는 토막글입니다.

이 문서는 토막글로 분류되는 800바이트 이하의 문서입니다. 토막글을 채우는 것은 기여자의 따뜻한 손길입니다. 이 틀을 적용할 시 틀의 매개변수로 분류:토막글의 하위 분류 중 적절한 분류를 지정해 주시기 바랍니다.

목차

개요

Spanning Tree

나무 반달인 줄 알았다면 오산이다.

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

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

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