MST | 최소 비용 신장 트리 (MST) 개념 간략한 정리

신장 트리 : n개 정점 무방향 그래프에서 간선 n-1개 부분 그래프

최소 비용 신장 트리

• 그래프에서 모든 노드 연결 시 사용하는 엣지 가중치 합 최소로 하는 트리
• n개 정점 갖는 무방향 그래프에서 모든 노드를 연결한 신장 트리 구성할 때 간선 가중치 합 최소인 트리
• MST는 엣지 가중치 최소를 사이클 없고, 단절점 없이 만드는 게 목표다.
• 에지를 기준으로 하는 알고리즘

[최소 비용 신장 트리 조건]
정점 n개
간선 n-1개
사이클 X : 사이클 포함 시 가중치 합이 최소가 될 수 없으므로 뺀다.
단절점 없는 (연결 그래프)

→ 최소비용 신장트리를 구현할 알고리즘의 종류

1) 크루스칼 (Kruskal) 알고리즘

• 모든 간선 가중치 오름차순 정렬 후, 모든 정점이 연결될 때까지 계속해서 작은 가중치를 사이클 형성 안되도록 N-1개까지 잇는 방식이다.
• 오름차순 정렬된 간선들 중에서 매번 차례대로 가장 작은 가중치 간선을 순서대로 연결한다.

동작 원리

1. 모든 간선들의 가중치를 오름차 순으로 정렬
2. 가중치가 가장 작은 간선을 선택
3. 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다.
4. 이 과정을 반복

---

2) 프림 알고리즘

• 시작 정점을 기준으로 가장 작은 간선과 연결된 정점을 선택하며 신장트리를 단계적 확장시키는 알고리즘이다.
• 정점 선택을 기반으로 하는 알고리즘
• 임의의 정점을 시작점으로 잡고, 아직 연결되지 않은 정점들에 대해 최소 가중치 갖는 정점을 연결하며 단계적으로 트리를 확장해간다

동작 원리

• 임의의 간선을 선택
• 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택
• 모든 정점이 선택될 때까지 반복

→ 그래프 내의 간선 많은 경우는 프림이, 간선 적은 경우 크루스칼이 유리하다고 한다.