최소 신장 트리(MST, 크루스칼, 프림 알고리즘) 최소 신장 트리(Minnimum Spanning Tree) spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리. 신장 트리(Spanning Tree)란 그래프 내의 모든 정점을 포함하는 트리 최소 연결 : 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개 이고, (n-1)개의 간선으로 연결 되어이으면 필연적으로 트리형태가 되고 이게 신장 트리이다. 즉 그래프에서 일부 간선을 선택해서 만든 트리. DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Spanning Tree는 트리의 ..