[알고리즘] 최소 신장 트리(Minimum Spanning Tree)

최소 신장 트리(Minimum Spanning Tree) 신장 트리(Spanning Tree)는 그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프를 의미합니다. n개의 정점이 있다면 신장 트리의 간선 수는 n-1개가 됩니다. 최소 신장 트리는 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리입니다. 가중치는 거리, 비용, 시간 등 여러가지로 응용할 수 있습니다. 최소 신장 트리의 대표적인 알고리즘으로는 프림 알고리즘(Prim’s Algorithm)과 크루스칼 알고리즘(Kruskal’s Algorithm)이 있습니다. 프림 알고리즘(Prim’s Algorithm) 프림 알고리즘은 로버트 프림(Robert C. Prim)이 만든 최소 신장 트리 알고리즘 입니다. 프림 알고리즘은 최소 신..