신장 트리

위키백과 ― 우리 모두의 백과사전.

평면 그래프 상에서의 최소 비용 신장 트리. 변에 비용이 주어진 평면 그래프 상에서 최소 비용 신장 트리가 어떤 식으로 나타나는지를 간략히 볼 수 있다.

연결된 무향 그래프에서 신장 트리(spanning tree, 걸침 나무)는 그 그래프의 부분 그래프이면서 모든 꼭지점을 연결하는 트리이다. 한 그래프에는 수많은 신장 트리가 있을 수 있다.

[편집] 최소 비용 신장 트리

최소 비용 신장 트리(minimum cost spanning tree)는 그래프의 각 변에 비용이 주어질 경우 신장 트리들 중에 비용이 최소인 것을 말한다. 아래의 알고리즘을 이용하면 최소 비용 신장 트리를 다항식 시간 내에 찾을 수 있다.

• 프림 알고리즘
• 크루스칼 알고리즘

[편집] 같이 보기

• 트리 구조