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

신장 트리(Spanning Tree)

신장 트리란, 사이클을 형성하지 않는 그래프를 말한다. 나는 부모님의 자식이 될 수 있지만 내 형제자매의 자식은 될 수 없는 것처럼, 사이클이 없다는 것은 부모-자식 관계만 형성된다는 것이고 따라서 신장 트리는 트리의 형태를 가지고 있다.

// 신장 트리의 특징
1. 그래프의 모든 정점이 간선에 의해 하나로 연결됨
2. 그래프 내에서 사이클 형성 X

(첫 번째 그래프도 오른쪽으로 90도 회전시키면 트리처럼 보임)

 

 

 

최소 신장 트리(Minimum Spanning Tree)

가중치가 있는 그래프에서도 신장 트리를 구성할 수 있는데, 신장 트리의 모든 간선의 가중치 합이 최소인 그래프를 최소 비용 신장 트리(Minimum Cost Spanning Tree) 또는 최소 신장 트리(Minimum Spanning Tree)라고 한다.

 위의 그림에서 왼쪽은 가중치가 있는 무방향 그래프이다. 여기서 신장 트리를 찾으면 오른쪽 형태가 된다.

우리가 눈으로 보기에는 당연히 0 -> 3 -> 2 -> 1로 가는 게 최소 비용이라는 것을 알 수 있지만, 어떻게 이걸 알고리즘으로 표현할까?

최소 신장 트리의 구성에 사용되는 알고리즘은 대표적으로 두 가지가 있다.

1. Kruskal Algorithm(크루스칼 알고리즘)
2. Prim Algorithm(프림 알고리즘)

 

 

 

Kruskal Algorithm

크루스칼(Kruskal) 알고리즘은 가중치를 기준으로 간선을 정렬한 후에 MST가 될 때까지 간선을 하나씩 선택 or 삭제해 나가는 방식이다.

1. 간선 선택에 의한 탐색 방법

MST가 될때까지 간선을 하나씩 선택해나가는 과정을 보자.

초기 그래프는 위의 그림과 같다. (모든 간선을 제거하고 시작하기 때문에 점선으로 표시)

 

제일 작은 가중치가 2이므로 이 간선을 추가하면 위와 같다.

 

다음으로 3을 추가하고,

 

차례대로 4와 6까지 추가하면 위와 같다. 

 

이제 7을 추가하면 될 차례인데, 그림 상으로도 보이듯이 C-D-E 간에 사이클이 생겼다! 이는 신장 트리의 규칙을 위반하기 때문에 C-E를 연결하는 간선은 추가하지 않고 다음 간선으로 넘어간다.

 

그런데 이때 새로 추가된 간선이 사이클인지는 어떻게 확인할까?

👉 Union-Find를 사용하면 된다.

연결된 노드들끼리 같은 집합이라고 표시해주면 되는데, 각 집합에서 노드 번호가 젤 작은 게 루트 노드가 되도록 설정하고 parent 배열에 루트 노드를 저장한다.

즉, parent [1] = 1, parent [2] = 1, parent [4] = 1은 1, 2, 4가 같은 집합에 속한다는 뜻이고 한 집합에 3개 이상의 원소가 있으므로 사이클을 형성하는 것!

 

이제 8을 추가하면 되는데, 추가된 간선의 수가 정점의 수보다 하나 적은 다섯 개가 됐기 때문에 더 이상 간선을 추가할 필요가 없다. 이미 이 자체만으로도 모든 노드를 방문하는 게 가능해졌기 때문! 여기서 우리는 최소 신장 트리(MST)의 특성을 알 수 있다.

간선의 수 + 1 = 정점의 수

 

따라서 이 그래프의 최소 신장 트리는 아래와 같이 완성된다.

 

2. 간선 제거에 의한 탐색 방법

MST가 될때까지 간선을 하나씩 제거해나가는 방법은 위의 방법과 정반대로 해주면 된다.

먼저 간선을 내림차순으로 정렬하고, 가중치가 큰 것부터 하나씩 제거해보면서 간선의 수 + 1 = 정점의 수가 될때까지 반복하면 된다.

단, 특정 간선을 제거했을 때 어떤 경로로도 방문할 수 없는 정점이 생긴다면 제거하지 말고 건너뛰어야 된다! 

 

 

 

Prim Algorithm

프림 알고리즘은 특정 정점을 시작으로 MST가 될 때까지 트리를 확장해나가는 방식이다. 시작점은 어떤 정점이든 상관없다.

특정 정점에서 시작해서 간선 비용이 적은 것부터 오름차순으로 선택여부를 결정하는데, 간선이 추가된 새로운 트리를 기준으로 다음 최저 비용 간선을 찾아나가야 한다. 그림으로 이해해보자.

 시작점이 5인 경우, 후보 간선의 가중치는 6, 10, 14이고 6이 제일 작으므로 5-6의 간선을 추가한다.

 

정점 6이 추가되었고, 이 트리를 기준으로(초록색) 후보 간선을 찾으면 위와 같다. 여기서 최저 비용은 10이므로 3-5의 간선을 추가한다.

 

정점 3이 추가되었고, 다시 새로운 트리를 기준으로 후보 간선을 추가한 후 최저 비용 간선을 찾으면 4이다. 따라서 3-4의 간선을 추가한다.

 

정점 4가 추가되었고, 다음으로 7의 비용을 가진 2-3 간선을 추가한다.

 

정점 2가 추가되었고, 최소 비용을 가진 1-2 간선을 추가한다.

 

정점 1이 추가되었고, 새로운 트리에서 최소 비용 간선은 비용 8을 가진 1-3이다. 하지만 1-3 간선을 추가할 경우 1-2-3 사이에 사이클이 형성되기 때문에 1-3은 추가할 수 없다.

그럼 8 다음으로 작은 게 9인데, 비용 9를 가진 2-4 간선을 추가하는 경우에도 사이클이 형성되기 때문에 추가할 수 없다. 마찬가지의 이유로 3-6의 간선도 추가할 수 없다.

따라서 그 다음 최소 비용 간선인 5-7을 추가한다.

 

정점 7이 추가되었고, 후보 간선은 7-8 하나밖에 없으므로 해당 간선을 추가한다.

 

정점 8까지 추가되었고, 간선이 n-1개가 되었으므로 드디어 탐색을 종료하면 된다.

따라서 이 그래프의 최종 신장 트리는 아래와 같은 형태가 된다.

 

 

 

References

📖 윤성우의 열혈 자료구조

📖 자료구조 개념 및 표현