MST (Minimum Spanning Tree)
MST는 그래프 내에서 모든 노드를 최소의 가중치로 연결하는 트리입니다. Kruskal 알고리즘과 Prim 알고리즘은 MST를 구하는 대표적인 방법입니다.
Kruskal 알고리즘
- 모든 간선을 가중치에 따라 정렬합니다.
- 가장 가중치가 작은 간선부터 선택하면서 트리를 만듭니다. 단, 사이클을 형성하는 간선은 제외합니다.
- 모든 노드가 연결될 때까지 반복합니다.
Prim 알고리즘
- 시작 노드를 선택하고, 이 노드를 MST에 포함시킵니다.
- 선택된 노드와 연결된 간선 중, MST에 포함되지 않은 노드와 연결된 가장 작은 간선을 선택합니다.
- 해당 노드를 MST에 포함시킵니다.
- 모든 노드가 MST에 포함될 때까지 2-3 단계를 반복합니다.
ST (Spanning Tree)
ST는 그래프의 모든 노드를 포함하면서 사이클이 없는 부분 그래프입니다. MST는 ST 중에서 가중치의 합이 최소인 트리입니다.
ST 구현 방법
- DFS (깊이 우선 탐색) 또는 BFS (너비 우선 탐색)을 사용하여 그래프를 탐색하면서 트리를 만듭니다.
- 탐색을 하면서 이미 방문한 노드는 건너뛰어 사이클을 피합니다.
비교
- MST는 가중치를 최소화하는 것에 초점을 둔다면, 일반적인 ST는 그래프의 모든 노드를 단순히 연결만 합니다.
- MST는 ST를 구하는 특별한 경우입니다. 즉, 모든 MST는 ST이지만, 모든 ST가 MST인 것은 아닙니다.
각 알고리즘은 문제의 요구사항에 따라 적절히 선택하면 됩니다. 예를 들어, 가중치를 고려해야 하는 네트워크 설계 문제에는 MST 알고리즘이, 단순히 모든 노드를 연결만 하면 되는 경우에는 일반적인 ST 알고리즘을 사용할 수 있습니다.
