스패닝 트리란?
스패닝 트리는 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클은 존재하지 않는 ‘부분’ 그래프를 의미한다.
즉, 0~4번 노드들 간에 서로 연결은 되어 있되, 자기 자신으로 돌아오는 간선이 있는 사이클이 존재해서는 안된다.
때문에 간선의 수 = 노드의 수 - 1 이 된다.
최소 스패닝 트리란?
이 그래프에서 B → G의 최솟값을 구한다고 생각해보자. 일단 B → G로 가는 방법은 다양하다.
1.
B → G
2.
B → D → E → G
3.
B → D → E → F → G
…
방법은 다양하지만, 간선에 부여된 가중치에 따라 어떤 방식이 가장 최소 비용의 가중치로 목적지까지 도달하는지는 정해져있다. 그 경로를 찾아내는 것이 최소 스패닝 트리이다. 이를 찾기위한 대표적인 알고리즘은,
•
크루스칼(Kruskal) 알고리즘
•
프림(Prime) 알고리즘
의 2가지가 있다.
크루스칼 알고리즘 - 1
1.
그래프의 모든 간선을 가중치에 따라 내림차순으로 정렬한다.
2.
그래프에서 가중치가 가장 높은 간선을 제거한다. 단, 이때 정점을 그래프에서 분리시키는 간선은 제거할 수 없기에 이런 경우에는 그 다음 가중치가 높은 간선을 제거한다.
3.
그래프의 간선이 n-1개만 남을 때까지 과정 2를 반복한다.
4.
그래프의 간선이 n-1개만 남으면 최소 스패닝 트리가 완성된다.
크루스칼 알고리즘 - 2
1.
그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
2.
그래프에 가중치가 가장 낮은 간선을 삽입한다. 단, 이때 사이클을 형성하는 간선은 삽입할 수 없으므로 그 다음 가중치가 낮은 간선을 삽입한다.
3.
그래프의 간선이 n-1개가 될때까지 과정 2를 반복한다.
4.
그래프의 간선이 n-1개가 되면 최소 스패닝 트리가 완성된다.
구현 요소
•
간선 리스트
•
정렬 (오름차순)
•
유니온 파인드(Disjoint Set) → 사이클 검사
시간복잡도
O(E log E) → E는 간선 수
1.
초기 상태 : 그래프 G10의 간선 가중치에 따라 오름차순으로 정렬되어 있고, 그래프 G10은 정점만 있다.
2.
가중치가 가장 낮은 간선 (E, G) 삽입 ⇒ 삽입한 간선 수 1개
3.
나머지 간선 중 가중치가 가장 낮은 간선 (A, B) 삽입 ⇒ 삽입한 간선 수 2개, 아래의 과정에서 이를 반복.
4.
나머지 간선 중 가중치가 가장 낮은 간선 (A, D) 삽입 ⇒ A-B-D-A 사이클 발생 ⇒ 삽입 불가
따라서 그 다음으로 가중치가 낮은 간선 (C, F) 삽입 ⇒ 삽입한 간선 수 5개
5.
나머지 간선 중 가장 가중치가 낮은 간선 (D, E) 삽입 ⇒ 삽입한 간선 수 6개 = 전체 노드 개수(7개) - 1
따라서 알고리즘 종료.
3. 프림 알고리즘
간선을 정렬하지 않고 하나의 정점에서 시작하여 트리를 확장해 나가는 방법이다.
1.
그래프에서 시작 정점을 선택한다.
2.
선택한 정점에 인접한모든 간선 중 가중치가 가장 낮은 간선을 연결하여 트리를 완성한다.
3.
이전에 선택한 정점과 새로 확장된 정점 모두에 인접한 간선 중 가중치가 가장 낮은 간선을 삽입한다. 단, 사이클을 형성하는 간선은 삽입할 수 없으므로 이런 경우에는 그 다음으로 가중치가 낮은 간선을 선택한다.
4.
그래프의 간선이 n-1개 삽입될 때까지 과정 3을 반복한다.
5.
그래프의 간선이 n-1개가 되면 최소 스패닝 트리가 완성된다.
구현 요소
•
우선순위 큐 (PriorityQueue)
•
visited 배열 또는 MST 집합
시간복잡도
•
O(E log V) 또는 O(V²) (인접행렬)
1.
시작 정점 A를 선택한다.
2.
A와 인접한 간선들 중 가중치가 가장 낮은 간선은? 3 ⇒ A-B 연결
a.
A, B 두 정점에 인접한 간선들 중 가중치가 가장 낮은 간선은? 5 ⇒ A-B-D 연결
b.
A, B, D 모두에 인접한 간선들 중 가중치가 가장 낮은 간선은? 6
but 6을 연결하면 A-B-D-A 사이클 발생 ⇒ SKIP
c.
그 다음 가중치가 낮은 간선은? 9
… 반복
3.
모든 정점들을 연결하면 종료
