생성나무
최근 수정 시각: (5년 전)
분류
Spanning Tree
생성 트리, 신장 트리라고도 한다. 사실상 다 같은 개념을 지칭하는 말이다.
그래프에서 모든 꼭지점(노드)를 포함하는 트리이다. 한 그래프는 여러 생성 나무를 가질 수 있지만, 반드시 모두 연결되어 있어야 하며, 연결되어 있지 않다면 생성 숲(Spanning Forest)이 되어 버린다.
네트워크, 통신망, 관계 시설 등을 계산하는 데 매우 유용한 개념이다. 최소 비용으로 통신망을 잇는 문제를 푸는 데 쓰이거나 한다. 이 중에서 특히 최솟값을 가지는 최소 비용 생성 나무는 영어로 Minimum Spanning Tree라고 하며, 크러스컬 알고리즘이나 프림 알고리즘으로 찾을 수 있다.
사실 다익스트라 알고리즘도 뜯어보면 내부적으로 생성나무를 일단 만들어서 쓴다.
생성 트리, 신장 트리라고도 한다. 사실상 다 같은 개념을 지칭하는 말이다.
그래프에서 모든 꼭지점(노드)를 포함하는 트리이다. 한 그래프는 여러 생성 나무를 가질 수 있지만, 반드시 모두 연결되어 있어야 하며, 연결되어 있지 않다면 생성 숲(Spanning Forest)이 되어 버린다.
네트워크, 통신망, 관계 시설 등을 계산하는 데 매우 유용한 개념이다. 최소 비용으로 통신망을 잇는 문제를 푸는 데 쓰이거나 한다. 이 중에서 특히 최솟값을 가지는 최소 비용 생성 나무는 영어로 Minimum Spanning Tree라고 하며, 크러스컬 알고리즘이나 프림 알고리즘으로 찾을 수 있다.
사실 다익스트라 알고리즘도 뜯어보면 내부적으로 생성나무를 일단 만들어서 쓴다.
라이선스를 별도로 명시하지 않은 문서는 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다.
기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권을 갖습니다.
문서의 기여자는 역사 탭에서 확인할 수 있습니다.
접두어의 N: - 나무위키 사용자, R: - 리그베다 위키의 사용자를 뜻합니다.
자세한 사항은 나무위키에서 동일한 문서의 역사를 참고하시기 바랍니다.