Spanning Tree 개념: 모든 노드가 연결되어 있으며 트리의 속성을 만족하는 그래프 특징 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트리의 속성을 만족시킴 (사이클이 존재하지 않음) Minimum Spanning Tree(MST) 최소 신장 트리 개념: Spanning Tree 중 간선의 가중치 합이 최소인 것 알고리즘 종류 Kruskal’s algorithm Prim's algorithm