최소 비용 신장 트리 (MST)
- 그래프에서 최소 비용 문제
1) 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리
2) 두 정점 사이의 최소 비용의 경로 찾기 - 신장 트리
: n개의 정점으로 이뤄진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 - 최소 신장 트리(MST)
: 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리
Prim 알고리즘
-
Prim 알고리즘
: 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식
1) 임의 정점을 하나 선택해서 시작
2) 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
3) 모든 정점이 선택될 때까지 1,2 과정을 반복 -
Prim 알고리즘 코드 (BFS + priority queue)
import sys
sys.stdin = open('input.txt', 'r')
# 우선순위큐 활용
from heapq import heappush, heappop
def prim(start):
pq = []
MST = [0] * V
# 최소 비용
sum_weight = 0
# 시작점 추가
# [기존 BFS] 노드 번호만 관리
# [Prim] 가중치가 낮으면 먼저 나와야 한다
# => 관리해야 할 데이터: 가중치, 노드 번호 (2가지)
# => 동시에 두 가지 데이터 다루기
# 1. class로 만들기
# 2. 튜플로 관리
heappush(pq, (0, start))
while pq:
weight, now = heappop(pq)
# 우선순위큐 특성 상, 더 먼 거리로 가는 방법이 큐에 저장되어 있기 때문에
# 기존에 이미 더 짧은 거리로 방문했다면, continue
if MST[now]:
continue
# 방문 처리
MST[now] = 1
# 누적합 추가
sum_weight += weight
# 갈 수 있는 노드들을 보면서
for to in range(V):
# 갈 수 없거나 이미 방문했다면 pass
if graph[now][to] == 0 or MST[to]:
continue
heappush(pq, (graph[now][to], to))
print(f'최소 비용: {sum_weight}')
V, E = map(int, input().split())
# 인접 행렬로 저장
graph = [[0] * V for _ in range(V)]
for _ in range(E):
s, e, w = map(int, input().split())
# ex) graph[3][4] = 31 => 3에서 4로 가는 데 31이라는 비용이 든다.
# 가중치 저장
graph[s][e] = w
graph[e][s] = w
prim(0)
#print(graph)Kruskal 알고리즘
- kruskal 알고리즘 코드
import sys
sys.stdin = open('input.txt', 'r')
# 1, 전체 그래프를 보고, 가중치가 제일 작은 간선부터 뽑자
# 코드로 구현?: 전체 간선 정보를 저장 + 가중치로 정렬
# 2. 방문 처리
# 이 때, 싸이클이 발생하면 안 된다
# 싸이클 여부?: union-find 알고리즘 활용
def find_set(x):
if parents[x] == x:
return x
# 경로 압축
parents[x] = find_set(parents[x])
return parents[x]
def union(x, y):
x = find_set(x)
y = find_set(y)
# 같은 집합이면 pass
if x == y:
return
if x < y:
parents[y] = x
else:
parents[x] = y
V, E = map(int, input().split())
edges = [] # 간선 정보들을 모두 저장
for _ in range(E):
s, e, w = map(int, input().split())
edges.append([s, e, w])
edges.sort(key=lambda x: x[2]) # 가중치를 기준으로 정렬
parents = [i for i in range(V)] # 대표자 배열 (자기 자신을 바라봄)
sum_weight = 0 # 총 가중치를 더할 변수
# 간선들을 모두 확인
for s, e, w in edges:
# 싸이클이 발생하면 pass
# -> 이미 같은 집합에 속해 있다면 pass
if find_set(s) == find_set(e):
print(s, e, w, '/ 싸이클 발생! 탈락!')
continue
print(s, e, w) # union 하는 순서
# 싸이클이 없으면 방문 처리
union(s, e)
sum_weight += w
print(f'최소 비용 = {sum_weight}')최단 경로 (Dijkstra)
- Dijkstra 알고리즘 코드
import sys
sys.stdin = open('input.txt', 'r')
from heapq import heappush, heappop
INF = int(1e9)
V, E = map(int, input().split())
start = 0 # 시작 노드 번호
# 인접 리스트
graph = [[] for _ in range(V)]
# 누적 거리를 저장할 변수
distance = [INF] * V
# 간선 정보 저장
for _ in range(E):
s, e, w = map(int, input().split())
graph[s].append([w, e])
def dijkstra(start):
pq = []
# 시작점의 weight, node 번호를 한 번에 저장
heappush(pq, (0, start))
# 시작 노드 초기화
distance[start] = 0
while pq:
# 최단 거리 노드에 대한 정보
dist, now = heappop(pq)
# pq의 특성 때문에 더 긴 거리가 미리 저장되어 있음
# now가 이미 처리된 노드라면 pass
if distance[now] < dist:
continue
# now에서 인접한 다른 노드 확인
for to in graph[now]:
next_dist = to[0]
next_node = to[1]
# 누적 거리 계산
new_dist = dist + next_dist
# 이미 더 짧은 거리로 간 경우 pass
if new_dist >= distance[next_node]:
continue
distance[next_node] = new_dist # 누적 거리를 최단 거리로 갱신
heappush(pq, (new_dist, next_node)) # next_node의 인접 노드들을 pq에 추가
dijkstra(0)
print(distance)- 강사님 강의!
'''
7 11
0 1 32
0 2 31
0 5 60
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51
'''
V, E = map(int, input().split())
# 그래프 저장: 인접 리스트
graph = [[] for _ in range(V)]
# 간선 정보를 인접 리스트에 저장
for _ in range(E):
u, v, w = map(int, input().split()) # u -> v 간선의 가중치가 w
graph[u].append((v, w)) # v로 가는 간선의 가중치가 w
graph[v].append((u, w))
import heapq #최소 힙
# Prim 알고리즘 함수 정의
# graph: 인접 리스트, start: 시작 정점
def prim(graph, start):
# 정점에 대해 방문 체크 배열
visited = [False] * V
mheap = [] # 최소 힙: 최소 힙을 통해 지금까지 연결된 간선들 중 최소 비용 간선을 선택
# 최소 신장 트리를 저장할 리스트
mst = []
# 시작 정점으로부터 간선을 선택 시작하도록 초기값을 넣어준다
# (가중치, 다음으로 가는 정점)
heapq.heappush(mheap, (0, start))
while mheap:
# 최소 비용을 가진 간선을 하나씩 꺼내면서 진행
weight, node = heapq.heappop(mheap)
# 방문 체크 (이미 연결한 노드라면 무시)
if visited[node]:
continue
visited[node] = True # 해당 정점에 방문 표시
mst.append((weight, node)) # 최소 신장 트리에 해당 간선 정보를 추가
# 해당 node와 연결되어 있는 모든 간선 정보를 최소 힙에 추가
for nxt, weight in graph[node]:
if not visited[nxt]:
heapq.heappush(mheap, (weight, nxt)) # 연결된 간선 정보를 최소 힙에 추가
return mst
mst = prim(graph, 0)
print(mst)
멋쟁이 토마토 개발자 🍅