7주차: 최소신장트리, 최단경로 알고리즘
📚 쉽게 배우는 자료구조 with python
최소 신장 트리 (MST)
정점 집합 V와 간선 집합 E로 구성된 그래프 G = (V,E)의 최소 간선 수는 (V - 1)
일반적으로 트리가 "싸이클이 없는 연결된 그래프"라는 점과 모든 트리는 |V| - 1 개의 간선을 가진다는 점에서, 트리를 "최소한의 간선을 사용하며 연결된 그래프" 라고 정의할 수도 있다.
Spanning Tree (신장 트리)
- Spanning Tree : 연결 그래프 G = (V, E)에서 V는 그대로 두고, E = |V| - 1 으로 만든 것
- 신장 트리의 비용: 신장 트리를 구성하는 간선의 가중치를 다 더한 것
- 최소 신장 트리 (Minimum Spanning Tree): 가중치가 있는 무방향 그래프 G로부터 만들 수 있는 모든 신장 트리 중, 비용이 가장 낮은 트리를 최소 신장 트리
MST를 찾는 방법
1. 프림 알고리즘 (Prim Algorithm)
- 아무 간선도 없는 상태에서
- 인접 정점 중 최소 비용인 정점에 간선을 하나씩 더해나가는 작업을
- (V-1)개의 간선이 생길 때까지 반복
👉🏻 프림 알고리즘의 Pseudo Code
: 정점 u를 신장 트리에 포함시키는 데에 드는 최소 비용 저장
Prim(G, r):
S <- {r}
r.cost <- 0
for each u in (V-{r})
u.cost <- w
while (S != V)
u <- deleteMin(V-S)
S = S+{u}
for each v in u.adj
if (v in (V-S) and w < v.cost)
v.cost <- w
v.tree <- u
deleteMin(Q):
집합 Q에서 u.cost값이 가장 작은 정점 u를 삭제하면서 리턴- r : 시작 정점
- S : 정점 집합, 처음엔 시작정점 r로 시작해서 하나씩 더해진다.
- 정점을 하나 더할 때, 대응되는 간선이 하나씩 더해진다.
- u.adj: 정점 u에 인접한 정점들의 집합
❗️ 프림 알고리즘의 시간 복잡도 : O(ElogV)
2. 크루스칼 알고리즘 (Krusckal Algorithm)
- 모든 간선을 비용이 작은 순서로 정렬
- 모든 정점을 n개의 집합으로 초기화
- 비용이 작은 간선부터 하나씩 살피며 사이클을 생성하지 않는지 체크, 생성한다면 그 간선은 버리고 아니면 두 집합을 합침
- 이러한 과정을 (V-1)개의 간선이 생길 때까지 반복
👉🏻 크루스칼 알고리즘 Pseudo Code
Kruskal(G):
T <- []
각각 단 하나의 정점만으로 이루어진 n개의 집합 초기화
모든 간선을 가중치의 크기순으로 정렬하여 배열 A에 저장
while (T의 간선수 < n-1)
A에서 최소비용 간선 제거
if (정점 u가 v와 다른 집합에 속함)
간선 (u-v)를 더함
u v 집합을 하나로 합침❗️ 크루스칼 알고리즘의 시간 복잡도 : O(ElogV)
두 방법의 비교
공통점
- 간선이 하나도 없는 상태에서 간선을 하나씩 더해나감
- 정점의 집합을 키워나가는 과정에서 간선의 집합도 커짐
차이점
- 프림 알고리즘은 '하나의'정점 집합(S)를 점점 키워나감
- 크루스칼 알고리즘은 '여러'정점 집합을 운영하여 집합을 합쳐나감
최단 경로 알고리즘
다음주 내용 보충 예정...
한 정점에서 다른 정점으로 가는 길 중 가장 빠른 길을 구하는 알고리즘이다.
다익스트라 알고리즘
모든 가중치가 음이 아닌 일반적인 경우, 다익스트라 알고리즘을 사용해 최단 경로를 구한다.
👉🏻 다익스트라 알고리즘 Pseudo Code
Dijkstra(G, r):
S <- {r}
r.cost <- 0
for each u in V-{r}
u.cost <- w
while (S != V)
u <- deleteMin(V-S)
S <- S U {u}
for each v in u.adj
if (v in V-S and u.cost + w < v.cost)
v.cost <- u.cost + w
v.prev <- u
deleteMin(Q):
집합 Q에서 u.cost가 가장 작은 정점 u를 리턴- r: 시작 정점
- S : 정점 집합
- u.adj: 정점 u에 인접한 정점들의 집합
위의 슈도코드를 보면, 프림 알고리즘과 매우 유사하다. 다만 프림 알고리즘에서는 v.cost가 정점 v를 신장트리에 연결하는 '비용'을 저장하는 반면, 다익스트라 알고리즘에서는 시작정점 r에서 정점 v에 이르는 '거리'를 저장한다.
벨만-포드 알고리즘
음의 가중치가 존재하는 경우, 벨만-포드 알고리즘을 사용해 최단 경로를 구한다.
👉🏻 벨만-포드 알고리즘 Pseudo Code
BellmanFord(G, r):
for each u in V
u.cost <- \∞
r.cost <- 0
for i in 1 to n-1
for each (u → v) in E
if (u.cost + w < v.cost)
v.cost <- u.cost + w
v.prev <- u
for each (u → v) in E
if (u.cost+w < v.cost) output "해 없음: 음의 싸이클"- n: 정점의 총 갯수
- (u → v) : 방향 간선
정체되지 않는 성장