신장 트리(Spanning Tree)
- 그래프 내의 모든 정점(노드)가 연결된 그래프
- 간선의 수가 가장 적은 최소 연결 부분 그래프 이다.
- 모든 정점이 연결되어 있어야 하지만 사이클이 존재해서는 안되며, 연결되지 않은 정점이 없어야한다.
- n개의 정점(노드)를 가진 그래프의 간선의 수는 [ n-1 ]이다.
- 하나의 그래프에는 여러개의 신장 트리가 존재할 수 있다.
- DFS, BFS를 이용해 신장트리를 찾을 수 있다.
가중치 그래프(Weighted Graph)
- 정점 사이의 간선에 가중치가 부여된 그래프
- 그래프가 도로망을 나타낸다면 가중치는 거리 또는 두 지점 사이를 가는데 걸리는 시간을 얘기한다.
최소 신장 트리(Minimum Spanning Tree)
- 가중치 그래프의 신장 트리중 간선의 합이 가장 작은 신장 트리
이러한 최소 신장 트리를 찾는 알고리즘에는 프림(Prim) 알고리즘과 크루스칼(Kruskal) 알고리즘이 있다.
크루스칼(Kruskal) 알고리즘
- 간선 데이터를 가중치에 따라 오름차순으로 정렬한다.
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
1) 사이클이 발생하는 경우 해당 간선은 제외한다.
2) 사이클이 발생하지 않는 경우 해당 간선을 신장트리에 포함시킨다.- 오름차순으로 2의 과정을 반복해 최소 신장 트리를 완성시킨다.
크루스칼의 시간 복잡도
- Union-Find 알고리즘을 이용해 구현시 O(1)의 시간 복잡도를 가지기 때문에 간선을 정렬하는 시간에 따라 시간 복잡도가 달라진다.
- 가장 일반적인 퀵 정렬을 예로 들면, 퀵 정렬의 시간 복잡도인 O(ElogE)가 크루스칼 알고리즘의 시간 복잡도가 된다.
* E: 간선의 갯수
* Union-Find 알고리즘
: 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘
프림(Prim) 알고리즘
- 그래프에서 시작 정점을 선택한다.
- 선택한 정점과 연결된 간선 중 가장 낮은 가중치를 갖는 간선을 신장트리에 포함시킨다.
1) 단 사이클이 없는 간선만 포함한다.- 포함된 간선에 연결된 모든 정점에 대해 2번의 과정을 반복해 최소 신장 트리를 완성시킨다.
프림의 시간복잡도
- 우선순위 큐를 이용한 최소 힙으로 프림을 구현할 수 있다.
- 모든 노드를 탐색하는데 O(V)의 시간이 걸리고, 최소 간선을 찾는데 O(logV)의 시간이 걸려 탐색과정에서는 O(VlogV)의 시간이 소요된다.
- 각 노드의 인접 간선을 찾는 시간은 O(E)가 걸리며 간선을 힙에 넣는데 O(logV)의 시간이 소요되어 우선순위 큐 구성에 O(ElogV)의 시간이 소요된다.
- 따라서 O(VlogV+ElogV)의 시간이 되는데 E가 일반적으로 V보다 크기 때문에 VlogV를 무시하여 O(ElogV)가 프림 알고리즘의 시간복잡도가 된다.
* E: 간선의 갯수
* V: 노드의 갯수
크루스칼 VS 프림
두 알고리즘 모두 최소 신장 트리를 구하는 알고리즘이지만 동작 방식이 다르기 때문에 상황에 따라 사용해야한다.
크루스칼의 시간복잡도는 O(ElogE)이고, 프림의 시간복잡도는 O(ElogV)이기 때문에
그래프 내의 간선이 적은 경우 크루스칼 알고리즘이 유리하고,
간선이 많은 경우 프림 알고리즘 이 유리하다.
으쌰으쌰🐜🐜