개념

신장 트리 중에서 간선의 가중치 합이 가장 작은 트리

• 신장 트리 : 가중 무방향 그래프에서 모든 정점을 포함하는 연결된 트리

조건

• 무방향 연결 그래프
• 싸이클 없는 연결 그래프
• n개의 정점, n-1개의 간선

종류

• 크루스칼

  

  

• 프림