23-1 : 그래프의 최소 비용 문제 (1) - 최소 신장 트리
작성:
최소 신장 트리 문제
1. 그래프에서 최소 비용 문제
a. 최소 신장 트리 문제
- 가중치 그래프에서 모든 정점들을 연결하는 간선들의 가중치의 합이 최소가 되는 트리를 찾는 문제.
b. 최단 경로 문제
- 시작 정점에서 목표 정점까지 가는 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제.
2. 신장 트리란?
- 신장 트리 (Spanning Tree)
- n개의 정점을 포함하는 무향 그래프에서 n개의 정점과 n-1개의 간선으로 구성된 트리.
- 최소 신장 트리 (Minimum Spanning Tree)
- 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리.
- 최소 신장 트리를 찾는 알고리즘에는 대표적으로 프림과 크루스칼 알고리즘이 있다. 이 두 알고리즘은 모두 그리디 알고리즘이다.
3. 프림 알고리즘
a. 프림 알고리즘이란?
- 한 정점에 연결된 간선들 중 가중치가 가장 낮은 간선을 하나씩 선택하면서 최소 신장 트리를 만들어가는 방식이다.
- 시간복잡도: O(V² + E) (V: 정점의 개수, E: 간선의 개수)
(간선 (u, v)는 u가 트리에 추가될 때 한 번, v가 트리에 추가될 때 한 번 검사된다.)
b. 프림 알고리즘의 구현
- 최소 가중치를 저장하는 배열을 만들고, 트리에 정점을 새로 추가할 때마다 그 정점에 인접한 간선들을 순회하면서 갱신한다.
- 임의의 정점을 하나 선택해서 시작한다.
- 선택한 정점들과 인접하는 정점들 중에 최소 비용의 간선이 존재하는 정점을 선택한다.
- 모든 정점이 선택될 때까지 2번 과정을 반복한다.
# 프림 알고리즘
edges = [(0, 1, 32), (0, 2, 31), (0, 6, 51), (0, 5, 60), (1, 2, 21), (2, 4, 46),
(6, 2, 25), (6, 4, 51), (3, 4, 34), (3, 5, 18), (5, 4, 40)]
graph = dict()
for edge in edges:
s, e, val = edge
if graph.get(s):
graph[s].append((e, val))
else:
graph[s] = [(e, val)]
if graph.get(e):
graph[e].append((s, val))
else:
graph[e] = [(s, val)]
for key in sorted(graph.keys()):
print(key, graph[key])
print('--------Graph--------')
# 그래프의 인접리스트 표현
N = len(graph.keys()) # N은 정점의 개수
def MST_PRIM(G, s): # G: 그래프, s: 시작 정점
minWeight = [float('inf') for i in range(N)] # 가중치를 무한대로 초기화
parents = [None for i in range(N)] # 트리에서 연결될 부모 정점 초기화.
# 각 정점이 실제 어떤 간선을 통해 트리와 연결되었는지를 확인하기 위해 사용한다.
visited = [0 for i in range(N)] # 정점 방문 여부 초기화
minWeight[s] = 0 # 시작 정점의 가중치를 0으로 설정한다.
# 또한, 이 설정은 시작 정점을 방문하겠다고 표시하기 위한 장치가 된다.
for i in range(N): # 정점의 개수 만큼 반복 (모든 정점을 방문할 때까지)
minidx, minval = -1, float('inf') # 최소 가중치 정점을 찾기 위한 초기화
# 여기서부터 방문하지 않은 정점 중 최소 가중치 정점 찾기
for j in range(N): # 새로 추가할 정점 찾기
if not visited[j] and minWeight[j] < minval:
minval = minWeight[j]
minidx = j
visited[minidx] = 1 # 최소 가중치 정점 방문 표시
# 여기서부터 추가한 정점에 인접한 간선에 대해 minWeight 갱신과정
for v, val in G[minidx]: # 새로 추가한 정점 인근의 간선 정보 갱신
if not visited[v] and val < minWeight[v]:
minWeight[v] = val
parents[v] = minidx
print(minidx, minval) # 새로 추가할 정점과 그 가중치
print(visited, minWeight, parents)
# 정점의 방문 정보, 갱신한 가중치 정보, MST
print('----------------')
return parents, sum(minWeight)
print(MST_PRIM(graph, 0))
# 출력
0 [(1, 32), (2, 31), (6, 51), (5, 60)]
1 [(0, 32), (2, 21)]
2 [(0, 31), (1, 21), (4, 46), (6, 25)]
3 [(4, 34), (5, 18)]
4 [(2, 46), (6, 51), (3, 34), (5, 40)]
5 [(0, 60), (3, 18), (4, 40)]
6 [(0, 51), (2, 25), (4, 51)]
--------Graph--------
0 0
[1, 0, 0, 0, 0, 0, 0] [0, 32, 31, inf, inf, 60, 51] [None, 0, 0, None, None, 0, 0]
----------------
2 31
[1, 0, 1, 0, 0, 0, 0] [0, 21, 31, inf, 46, 60, 25] [None, 2, 0, None, 2, 0, 2]
----------------
1 21
[1, 1, 1, 0, 0, 0, 0] [0, 21, 31, inf, 46, 60, 25] [None, 2, 0, None, 2, 0, 2]
----------------
6 25
[1, 1, 1, 0, 0, 0, 1] [0, 21, 31, inf, 46, 60, 25] [None, 2, 0, None, 2, 0, 2]
----------------
4 46
[1, 1, 1, 0, 1, 0, 1] [0, 21, 31, 34, 46, 40, 25] [None, 2, 0, 4, 2, 4, 2]
----------------
3 34
[1, 1, 1, 1, 1, 0, 1] [0, 21, 31, 34, 46, 18, 25] [None, 2, 0, 4, 2, 3, 2]
----------------
5 18
[1, 1, 1, 1, 1, 1, 1] [0, 21, 31, 34, 46, 18, 25] [None, 2, 0, 4, 2, 3, 2]
----------------
([None, 2, 0, 4, 2, 3, 2], 175)
# 최종적으로 프린트된 리스트는 최소 신장 트리를 의미하고
# 값은 그 MST의 가중치를 나타낸다.
4. 크루스칼 알고리즘
a. 크루스칼 알고리즘이란?
- 모든 간선 중 최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘.
- n개의 정점을 포함하는 그래프에서 n-1개의 간선을 선택하는 방식이다.
- 상호 배타적 집합을 통해 구현할 수 있다.
- 시간복잡도: O(ElogE) (E: 간선의 개수)
- 간선을 가중치의 오름차순으로 정렬하는 데 걸리는 시간이다.
b. 크루스칼 알고리즘의 구현
- 우선 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
- 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다.
- 이때 사이클이 존재하면 다음으로 가중치가 낮은 간선을 선택한다.
- 사이클이 있는지 확인하는 과정은 상호 배타적 집합 자료 구조를 통해 수행할 수 있다.
- n-1개의 간선이 선택될 때까지 2번 과정을 반복한다.
# 크루스칼 알고리즘
def Find(x):
if parents[x] == x:
return x
parents[x] = Find(parents[x])
return parents[x]
def Union(x, y):
xroot = Find(x)
yroot = Find(y)
if ranks[xroot] >= ranks[yroot]:
parents[yroot] = xroot
else:
parents[xroot] = yroot
if ranks[xroot] == ranks[yroot]:
ranks[xroot] += 1
def MST_KRUSKAL(G):
mst = [] # 최소 신장 트리
mst_cost = 0 # 최소 신장 트리의 가중치
G.sort(key=lambda x: x[2]) # 가중치의 오름차순으로 정렬
print(G) # 오름차순으로 정렬된 간선
while len(mst) < N-1:
s, e, val = G.pop(0)
if Find(s) != Find(e):
# 같은 집합에 속해있지 않다면 (사이클이 존재하지 않는다면)
Union(s, e) # 각각의 집합을 합친다.
mst.append((s, e)) # 그때의 간선을 MST에 저장
mst_cost += val # 그때의 가중치를 저장
print(s, e, val) # 선택된 간선과 그 가중치
print(parents, ranks) # 상호 배타 집합 정보
print('----------------')
return mst, mst_cost
edges = [(0, 1, 32), (0, 2, 31), (0, 6, 51), (0, 5, 60), (1, 2, 21), (2, 4, 46),
(6, 2, 25), (6, 4, 51), (3, 4, 34), (3, 5, 18), (5, 4, 40)]
N = 7 # N은 정점의 개수
parents = [i for i in range(N)]
ranks = [0 for i in range(N)]
print(MST_KRUSKAL(edges))
# 출력
[(3, 5, 18), (1, 2, 21), (6, 2, 25), (0, 2, 31), (0, 1, 32), (3, 4, 34),
(5, 4, 40), (2, 4, 46), (0, 6, 51), (6, 4, 51), (0, 5, 60)]
3 5 18
[0, 1, 2, 3, 4, 3, 6] [0, 0, 0, 1, 0, 0, 0]
----------------
1 2 21
[0, 1, 1, 3, 4, 3, 6] [0, 1, 0, 1, 0, 0, 0]
----------------
6 2 25
[0, 1, 1, 3, 4, 3, 1] [0, 1, 0, 1, 0, 0, 0]
----------------
0 2 31
[1, 1, 1, 3, 4, 3, 1] [0, 1, 0, 1, 0, 0, 0]
----------------
3 4 34
[1, 1, 1, 3, 3, 3, 1] [0, 1, 0, 1, 0, 0, 0]
----------------
2 4 46
[1, 1, 1, 1, 3, 3, 1] [0, 2, 0, 1, 0, 0, 0]
----------------
([(3, 5), (1, 2), (6, 2), (0, 2), (3, 4), (2, 4)], 175)
# 최종적으로 프린트된 리스트는 최소 신장 트리를 의미하고 값은 그 MST의 가중치를 나타낸다.
5. 알고리즘의 정당성 증명
- 프림 알고리즘 혹은 크루스칼 알고리즘이 선택하는 간선 중 최소 신장 트리 T에 속하지 않는 간선이 있다고 가정하자. 그 간선을 (u, v)라고 하자.
- T는 (u, v)를 포함하고 있지 않으므로 u와 v를 연결하는 다른 경로가 존재한다. (u와 v를 연결하는 다른 간선들이 존재한다.)
- T에서 u와 v를 연결하는 간선들 중 하나는 반드시 (u, v) 보다 가중치가 크거나 같다. (만약 (u, v)보다 모두 가중치가 적으면 프림 알고리즘 혹은 크루스칼 알고리즘이 그 간선을 선택할 수 밖에 없다.)
- T에서 (u, v)보다 가중치가 크거나 같은 그 간선을 (u, v)와 바꿔끼워도 T가 최소 신장 트리라는 가정 때문에 T는 (u, v)를 포함하는 최소 신장 트리가 된다.
-> 탐욕적 선택 속성 성립 - 이 속성은 마지막 간선을 추가해서 신장 트리가 될 때까지 성립하므로 마지막에 얻은 트리는 항상 최소 신장 트리가 된다.
-> 최적 부분 구조 성립
6. 시간복잡도 비교
- 프림 알고리즘: 시간복잡도: O(V² + E) (V: 정점의 개수, E: 간선의 개수)
- 크루스칼 알고리즘: 시간복잡도: O(ElogE) (E: 간선의 개수)
- 거의 모든 정점들 사이에 간선이 있는 밀집 그래프의 경우엔 E ≈ V² 이므로 이 경우엔 프림 알고리즘이 크루스칼 알고리즘보다 빠르게 동작한다.
출처: SW Expert Academy - Learn - Course - Programming Advanced &
알고리즘 문제 해결 전략
댓글남기기