그래프 (Graph) - 최소비용 신장 트리 (Minimum Cost Spanning Tree)

신장 트리

연결 그래프 G에서 모든 정점들을 포함하며 tree인 부분 graph

방법

임의의 정점에서 출발하여 DFS 또는 BFS로 graph 탐색 시,

정점 v에서 인접하며 방문되지 않은 정점 w가 존재할 때, 

간선 (v, w)의 집합 

 

 

가중치 무방향 graph에서 신장 트리 비용 = 신장 트리에 포함된 간선들의 비용

 

 

 

최소비용 신장 트리 (Minimum Cost Spanning Tree)

- 최소의 비용을 갖는 신장 트리

- ex) Kruskal, Prim, Sollin

 

조건

그래프 내의 간선들만 사용

n-1개의 간선만 포함

사이클 미포함

 

 

 

Kruskal	Prim
cycle check O	cycle check X