2월 26일-MST

MST란?

최소 신장 트리(Minimum Spanning Tree,MST)는 가중치가 부여된 무방향 그래프에서 모든 정점을 연결하면서 가중치의 합이 최소가 되는 트리를 말한다. 신장 트리는 그래프의 모든 정점을 포함하며 사이클이 없는 연결 부분 그래프이다. MST는 네트워크, 도로 건설, 회로 설계 등 다양한 분야에서 중요한 응용을 가진다.

MST 구하기: 크루스칼(Kruskal) 알고리즘

크루스칼 알고리즘은 가장 가벼운 간선부터 차례대로 선택하여 MST를 구성한다. 사이클을 형성하지 않는 한 간선을 선택하며 MST를 완성한다.

1. 간선 리스트 준비: 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
2. 초기화: 모든 정점을 독립된 집합으로 초기화한다.
3. 간선 선택: 정렬된 간선 리스트에서 순서대로 간선을 선택하며, 두 정점이 서로 다른 집합에 속해 있다면 두 집합을 합친다(Union-Find 알고리즘 사용). 이미 같은 집합에 속해 있다면, 선택한 간선은 사이클을 형성하므로 제외한다.
4. 종료 조건: 모든 정점이 하나의 집합에 속하게 되면 알고리즘을 종료한다.

MST 구하기: 프림(Prim) 알고리즘

프림 알고리즘은 특정 정점에서 시작하여 MST를 점진적으로 확장한다. 현재의 MST 집합에 인접한 간선 중 최소 가중치를 가진 간선을 선택하여 트리를 확장한다.

1. 초기화: 임의의 시작 정점을 선택하고, 해당 정점만이 포함된 집합을 만든다.
2. 간선 선택: 현재 MST 집합에 속한 정점들과 인접한 간선들 중에서 가장 가중치가 낮은 간선을 찾는다. 해당 간선이 연결하는 정점 중 하나가 MST 집합에 아직 포함되지 않은 정점이라면, 이 간선을 선택하고 해당 정점을 MST 집합에 추가한다.
3. 종료 조건: 모든 정점이 MST 집합에 포함될 때까지 2번 과정을 반복한다.

어떤 알고리즘을 선택할까?

• 크루스칼 알고리즘은 간선의 수가 적은 "희소 그래프(Sparse Graph)"에 적합하다.
• 프림 알고리즘은 간선의 수가 많은 "밀집 그래프(Dense Graph)"에 더 적합하다.

두 알고리즘 모두 MST를 구하는 유효한 방법이며, 구현의 복잡성, 그래프의 특성 및 사용 가능한 자료 구조에 따라 적합한 알고리즘을 선택할 수 있다.