최소 신장 트리 (Minimum Spanning Tree)

👑 신장 트리 (Spanning Tree)

신장 트리란 연결 그래프(Connected Graph)에서 모든 정점을 포함하면서, 사이클이 없는

트리를 말한다. 다시 말해, 그래프 내의 모든 정점을 포함하지만, 최소한의 간선만을 사용하여

그래프를 구성하는 트리이다. 하나의 그래프에는 여러 가지 신장 트리가 존재할 수 있다.

👑 최소 신장 트리 (Minimum Spanning Tree)

최소 신장 트리 (Minimum Spanning Tree, MST)는 주어진 그래프에서 모든 정점을 연결하는 트리

중에서, 간선의 가중치 합이 최소가 되는 트리이다. MST는 네트워크 설계, 클러스터링, 지도 제작 등의

다양한 분야에서 활용된다.

최소 신장 트리의 특징

• 사이클이 없음

  • 트리는 본래 사이클을 포함하지 않으므로, MST 또한 사이클을 포함하지 않는다.

• 연결성

  • MST는 주어진 그래프에서 모든 정점을 연결해야 한다.

• 최소 가중치

  • 가능한 모든 신장 트리 중에서 간선들의 가중치 합이 가장 작은 것을 말한다.

위의 그림에서 최소 신장 트리는 간선의 합이 10인 신장 트리이다. 위 그림 외에도 여러 개의 신장 트리가

존재할 수 있지만, 그들 중에서 최소 신장 트리는 간선의 합이 최소인 10이 되어야 한다. 또한, 간선의

가중치가 동일한 간선이 존재할 수 있으며, 최소 신장 트리는 한 그래프에서 하나만 존재하는 것이 아닌

여러 개가 있을 수 있다.

최소 신장 트리를 구하는 대표적인 알고리즘으로는 크루스칼 알고리즘 (Kruskal's Algorithm)과

프림 알고리즘 (Prim's Algorithm) 이 있다.

👑 크루스칼 알고리즘 (Kruskal’s algorithm)

크루스칼 알고리즘은 가중치 그래프가 주어졌을 때, MST를 찾기 위한 그리디 알고리즘 중 하나로

MST를 구하기 위해 간선을 오름차순으로 정렬하고, 트리 구조를 유지하며 간선을 선택해 나간다.

크루스칼 알고리즘은 Disjoint Set 자료구조를 사용해 사이클 유무를 효율적으로 검사하는 것이 특징이다.

크루스칼 알고리즘은 다음과 같이 동작한다.

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

2. 가중치가 가장 작은 간선부터 순서대로 선택한다.

3. 간선을 선택할 때 사이클이 형성되지 않도록 검사한다.

4. 트리의 간선 개수가 노드 개수 - 1개가 될 때까지 반복한다.

💡 동작 과정

위 그래프는 7개의 정점과 9개의 간선들을 가지고 있으며, MST는 7-1 = 6개의 간선들을 가져야 한다.

먼저 간선들을 오름차순 정렬하면:

이제 정렬된 간선들을 순서대록 선택하여, 현재 MST에 추가해도 사이클이 생기지 않는지를 확인한다.

• 사이클이 발생 O: 해당 간선 건너뜀

• 사이클이 발생 X: 해당 간선 MST에 추가

Step 1

간선 0-1을 선택, 사이클이 형성되지 않으므로 MST에 추가

Step 2

간선 1-6을 선택, 사이클이 형성되지 않으므로 MST에 추가

Step 3

간선 0-5을 선택, 사이클이 형성되지 않으므로 MST에 추가

Step 4

간선 5-4을 선택, 사이클이 형성되지 않으므로 MST에 추가

Step 5

간선 2-4을 선택, 사이클이 형성되지 않으므로 MST에 추가

Step 6

간선 5-6을 선택, 사이클이 형성되므로, 간선을 추가하지 않고 건너뛴다.

Step 7

간선 6-3을 선택, 사이클이 형성되지 않으므로 MST에 추가

MST의 간선의 개수가 노드 개수 - 1 = 6개가 되었으므로, 알고리즘을 종료한다.

💡 구현[C++, Java]

👑 프림 알고리즘 (Prim’s algorithm)

프림(Prim) 알고리즘은 MST를 찾는 방법 중 하나로, 가중치가 있는 연결 그래프에서 모든 정점을

포함하면서 가중치의 합이 최소가 되는 트리를 만드는 방법이다. 크루스칼 알고리즘이 간선을 중심으로

MST를 만드는 반면, 프림 알고리즘은 정점을 중심으로 MST를 확장해 나간다.

프림 알고리즘은 다음과 같이 동작한다.

1. 임의의 정점을 선택하여 MST에 추가하고 시작한다.

2. 현재 MST에 포함된 정점에서 인접한 정점 중 가장 작은 가중치를 가진 간선을 선택한다.

3. 선택한 간선에 연결된 새로운 정점을 MST에 추가한다.

4. 모든 정점이 MST에 포함될 때까지 2~3 단계를 반복한다.

이 과정에서, 이미 MST에 포함된 정점 집합과 아직 포함되지 않은 정점 집합 간의 최소 가중치 간선을

선택하는 방식으로 트리를 확장해 나간다.

💡 동작 과정

위 그래프에서 프림 알고리즘을 통해 MST를 구하는 과정은 다음과 같다.

Step 1

임의의 점을 선택하여 시작한다. (정점 0을 선택)

Step 2

현재 MST에 포함된 정점(0)에서 인접한 간선 0-1, 0-5 중 가중치가 가장 작은 0-1을 선택하고,

간선과 정점 1을 MST에 포함한다.

Step 3

현재 MST에 포함된 정점(0, 1)에서 인접한 간선 0-5, 1-6, 1-2 중 가중치가 가장 작은 1-6을

선택하고, 간선과 정점 6을 MST에 포함한다.

Step 4

현재 MST에 포함된 정점(0, 1, 6)에서 인접한 간선 0-5, 1-2, 5-6, 6-3 중 가중치가 가장 작은

0-5을 선택하고, 간선과 정점 5을 MST에 포함한다.

Step 5

현재 MST에 포함된 정점(0, 1, 5, 6)에서 인접한 간선 5-6, 1-2, 6-3, 5-4 중 가중치가 가장 작은

5-4을 선택하고, 간선과 정점 4을 MST에 포함한다.

Step 6

현재 MST에 포함된 정점(0, 1, 4, 5, 6)에서 인접한 간선 1-2, 6-3, 4-2, 4-3 중 가중치가 가장 작은

4-2을 선택하고, 간선과 정점 2을 MST에 포함한다.

Step 7

현재 MST에 포함된 정점(0, 1, 2, 4, 5, 6)에서 인접한 간선 6-3, 4-3 중 가중치가 가장 작은

6-3을 선택하고, 간선과 정점 3을 MST에 포함한다.

결과

💡 구현[C++, Java]