[알고리즘] 스패닝 트리와 최소 신장 트리

스패닝 트리(Spanning Tree)

스패닝 트리는 연결된 그래프에서 모든 정점을 포함하고, 그래프의 간선의 부분집합을 사용해 사이클 없이 연결된 구조입니다. 주요 특징으로는

• 스패닝 트리의 간선 개수는 정점 개수가 N 일 때 N - 1개입니다.
• 하나의 그래프에 여러 개의 스패닝 트리가 존재할 수 있습니다.

 

최소 신장 트리(MST, Minimum Spanning Tree)

최소 신장 트리는 연결 그래프에서 모든 정점을 포함하면서 최소 비용으로 연결된 부분 그래프입니다. 주요 특징으로는

• 그래프의 모든 정점이 연결되어야 합니다.
• 사이클이 없는 트리 형태를 가집니다.
• 간선의 가중치 합이 최소화됩니다.

최소 신장 트리를 찾기 위해 다음과 같은 알고리즘이 많이 사용됩니다.

 

크루스칼 알고리즘(Kruskal's Algorithm)

유니온-파인드(Union-Find) 알고리즘을 사용하여 사이클 여부를 판별하는 크루스칼 알고리즘입니다.

1. 간선을 가중치 순으로 정렬합니다.
2. 작은 가중치부터 간선을 선택해서 사이클이 생기지 않도록 합니다.

 

프림 알고리즘(Prim's Algorithm)

1. 하나의 정점에서 시작합니다.
2. 연결된 간선 중 가장 작은 가중치의 간선을 선택합니다.
3. 방문하지 않은 정점을 추가하며 간선 선택을 이어가며 MST를 확장합니다.