신장 트리(Spanning Tree)란?하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미 1. 모든 정점을 포함해야 한다.2. 연결 그래프이자 부분 그래프여야 한다.3. 사이클이 존재하지 않아야 한다. 최소 비용 신장 트리(Minimum Cost Spanning Tree)란?그래프에서 모든 노드를 연결할 때 간선의 가중치 합이 최소가 되는 경우의 신장 트리 최소 비용 신장 트리에는 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 존재한다. 크루스칼 알고리즘(Kruskal Algorithm)그리디 알고리즘을 통해 최소 신장 트리를 구하는 알고리즘이다.간선 데이터를 비용에 따라 오름차순으로 정렬한다.간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.사..
