그래프에서 Spanning Tree란 그래프의 모든 정점을 잇지만 사이클은 없는 부분 그래프를 의미한다. 즉, 형태와 관계없이 모든 정점을 사이클없이 이을수만 있다면, 그것이 곧 스패닝 트리이다. 스패닝 트리는 이름처럼 트리의 일종으로 V개의 모든 정점을 연결하는 간선의 수는 V-1개가 된다.
이때 최소 Spanning Tree(MST)는 이러한 스패닝 트리 중에서 간선의 가중치 합이 최소가 되는 스패닝 트리를 말한다. 즉, 간선의 가중치가 있을때 최소 스패닝 트리를 만들 수 있다.
그리고 이러한 최소 스패닝 트리를 구하는 알고리즘은 대표적으로 Kruscal과 Prim 알고리즘이 존재한다. 그럼 먼저 Kruscal 알고리즘에 대해서 알아보자.
Kruscal Algorithm
크루스칼 알고리즘은 간선들을 중심으로 그리디 알고리즘을 통해 최소 스패닝 트리를 구하는 알고리즘이다. 크루스칼 알고리즘의 동작 순서는 다음과 같다.
- 선택되지 않은 간선들 중 최소 가중치인 간선을 선택한다.
- 만약 그 간선을 선택했을 때, 지금까지 구성된 스패닝 트리에 사이클이 없을 경우에만 선택한다.
- 총 V - 1개의 간선이 선택될 때까지 반복한다.
이를 적용하여 예제 그래프를 단계별로 적용해보자. 빨간색 선으로 색칠이 되면, 최소 스패닝 트리의 간선으로 선택될 수 있는 간선이 선택된 것이다.
이때, 구성한 스패닝 트리에 사이클이 발생하는지에 대한 여부를 확인하기 위해서 분리 집합(Disjoint Set)을 사용한다. 이를 실제로 구현하기 위해서 Union-Find 알고리즘을 사용한다. 즉, 부모 노드가 서로 같은지를 확인해 같으면 사이클이 발생한다는 개념으로 이해하면 된다.
그런데 만약 어떤 간선을 선택했을 때, 그 간선의 두 정점이 같은 최상위 Parent를 갖는다면. 즉, 같은 그룹에 속했다면 Spanning Tree에 추가했을 때 사이클이 발생함을 의미한다.
Prim Algorithm
프림 알고리즘은 최소 스패닝 트리(MST)를 구하는 알고리즘으로 다음 순서로 동작한다.
- 최초 출발 노드와 연결되어 있는 간선들 중에서 가중치가 최소인 것을 선택해 MST에 추가한다. 이렇게 MST에는 2개의 정점이 포함되어 있다.
- MST에 포함된 모든 정점들과 연결된 간선들 중 가중치가 최소인 것을 선택해 MST에 추가한다.
- V - 1개의 간선이 선택될 까지 2번을 반복한다.
프림 알고리즘은 크루스칼 알고리즘과 다르게 정점을 중심으로 동작하므로 그래프 탐새과 유사하게 동작한다. 즉, 인접 리스트를 이용한 정점들간의 연결 관계가 필요하며, 이미 방문한 정점들에 대한 visited 정보를 기록한다. 각 정점들과 연결된 간선들 중 최소인 간선을 선택할때 우선순위 큐를 사용한다.
인용
https://4legs-study.tistory.com/111
최소 스패닝 트리 (MST) : 크루스칼 알고리즘 (Kruskal Algorithm)
최소 스패닝 트리 (MST, Minimum Spanning Tree) 그래프의 스패닝 트리(신장 트리, Spanning Tree)란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프를 의미한다. 위와 같은 그래프에서, 양쪽의 붉
4legs-study.tistory.com
'컴퓨터 사이언스 > Algorithm' 카테고리의 다른 글
| Dynamic Programming (0) | 2023.10.26 |
|---|---|
| 분리 집합(Disjoint Set): Union-Find (1) | 2023.10.21 |
| 최단 거리 알고리즘 정리 (1) | 2023.10.20 |
| 다익스트라(Dijkstra) (1) | 2023.10.19 |
| 위상 정렬 (1) | 2023.10.19 |
