한 버텍스를 기준으로 가능한한 작은 가중치의 아크들을 사용해서 모든 버텍스를 연결하는 트리를 만드는 겁니다. 즉, 최소의 아크 값만 사용해서 모든 버텍스를 연결하는 것을 의미한다.

그래프 G 의 spanning tree 중 edge weight 의 합이 최소인 spanning tree를 말한다.

spanning tree란 그래프 G 의 모든 vertex 가 cycle 이 없이 연결된 형태를 말한다.

따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다.

최소 신장 트리가 최단 경로는 아니다.

크루스칼 알고리즘과 프림 알고리즘을 알기 위해선 유니온 파인드 알고리즘을 알아야 한다.

Union-Find (Disjoint Set)

프림 알고리즘 (Prim Algorithm)

정점 기반 알고리즘 - 정점이 많고, 간선이 촘촘한 밀집 그래프(Dense Graph)에서 더 적합합니다.

1. 임의의 시작 정점에서 출발하여, 그 정점에서 연결 가능한 가장 낮은 가중치의 간선을 선택합니다.
2. 이미 선택한 정점에 연결된 미방문 정점들을 대상으로, 가중치가 가장 낮은 간선을 선택하여 MST에 포함시킵니다.
3. 모든 정점이 MST에 포함될 때까지 이 과정을 반복합니다.

Time Complexity

배열을 사용하면O(V^2), 이진 힙을 사용하면O(ElgV), 피보나치 힙을 사용하면**O(E+VlgV)**의 시간 복잡도를 가집니다.

크루스칼 (Kruskal Algorithm)

간선 기반 알고리즘 - 간선이 적고, 그래프가 연결될 가능성이 큰 희소 그래프(Sparse Graph)에서 유리합니다.

1. 모든 간선들의 가중치를 오름차순으로 정렬한다.

2. 가중치가 가장 작은 간선을 선택한다.