Spanning Tree
생성 트리, 신장 트리라고도 한다. 사실상 다 같은 개념을 지칭하는 말이다.
그래프에서 모든 꼭지점(노드)를 포함하는 트리이다. 한 그래프는 여러 생성 나무를 가질 수 있지만, 반드시 모두 연결되어 있어야 하며, 연결되어 있지 않다면 생성 숲(Spanning Forest)이 되어 버린다.
네트워크, 통신망, 관계 시설 등을 계산하는 데 매우 유용한 개념이다. 최소 비용으로 통신망을 잇는 문제를 푸는 데 쓰이거나 한다. 이 중에서 특히 최솟값을 가지는 최소 비용 생성 나무는 영어로 Minimum Spanning Tree라고 하며, 크러스컬 알고리즘이나 프림 알고리즘으로 찾을 수 있다.
사실 다익스트라 알고리즘도 뜯어보면 내부적으로 생성나무를 일단 만들어서 쓴다.