신장트리 (Spaning tree)

무방향, Cycle 없이, 최소가중치

프림,크루스칼,Greedy 알고리즘

간선수 = n-1(노드)

G(V,E)

 

#정의: 그래프 내의 모든 정점들이 연결되어 있고, 사이클을 포함하지 않은 트리

 

[개념] 모든 정점을 포함하고 순환되지 않으면서 가중치의 합이 최소가 되는 신장트리. 주어진 연결그래프에서 사이클을 형성하는 간선을 제거하여 만든 트리

- 정점과 간선으로 구성된 무방향 그래프 G(V,E)에서 사이클없이 그래프상의 모든 정점들을 연결한 가중치의 합이 최소가 되는 신장 트리

[특징]

1)그래프 내 모든 정점 포함

2)n개의 정점일 때, n-1개의 간선

3)사이클 無

4)간선가중치의 합 최소화

 

[유형]

1)Prim(시작정점부터 단계적 확장)

2)Kruskal(간선비용 정렬후 최소비용 간선부터 선택확장)

3)Solin(각 정점별 최소간선 모두 연결 후, 트리연결 최소간선 선택)

 

[트리구축과정] 그래프의 간선들을 가중치의 오름차순으로 정렬

[활용] NW 최적경로 설계, 도로 설계