n 개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리
최소신장 트리 (Minimum Spanning Tree)
무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리
MST 표현
그래프
간선들의 배열
인접 리스트
부모 자식관계와 가중치에 대한 배열 (트리)
Prim 알고리즘
하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식
임의 정점을 하나 선택해서 시작
선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
모든 정점이 선택될 때까지 1, 2번 과정을 반복
서로소인 2개의 집합(2 disjoint-sets) 정보를 유지
트리 정점들(tree vertices) - MST를 만들기 위해 선택된 정점들
비트리 정점들(non-tree vertices) - 선택 되지 않은 정점들
알고리즘 적용 예시
알고리즘
# 프림 알고리즘
def mst_prim(g, r):
# 최소 가중치를 갱신하는 리스트
key = [float('inf') for _ in range(v+1)]
# 최소 가중치를 위해 어떤 노드와 연결한지 정보를 담는 리스트
pi = [None for _ in range(v+1)]
# 방문 여부
visited = [0 for _ in range(v+1)]
# 시작 정점의 가중치는 0으로 초기화
key[r] = 0
for _ in range(v+1): # 모든 정점(정점의 개수만큼)을 순회
# 최소 key(가중치) 찾기
min_key = float('inf')
start = -1
for i in range(v+1):
# 방문하지 않은 노드중 최소의 가중치를 지닌 인접 정점을 탐색
if key[i] < min_key and not visited[i]:
min_key = key[i]
start = i
# 방문하지 않은, 최소의 가중치 정점에 대해서만 방문 표시
visited[start] = 1
# 선정된 정점을 기준으로 인접한 정점의 가중치를 탐색
for next_v, next_w in g[start]:
# 기존 key 리스트의 가중치보다 탐색 중 나온 가중치가 더 적고
# 방문하지 않은 정점이라면 갱신
if next_w < key[next_v] and not visited[next_v]:
key[next_v] = next_w
pi[next_v] = start
return sum(key)
for tc in range(1, int(input())+1):
v, e = map(int, input().split()) # v: 마지막 노드 번호, e: 간선의 개수
g = {} # 그래프 생성
# 그래프 생성 g = { 정점1: {(인접 정점, 가중치), ...}, 정점2: ...}
for i in range(e):
n1, n2, w = map(int, input().split())
if n1 not in g:
g[n1] = set()
if n2 not in g:
g[n2] = set()
g[n1].add((n2, w))
g[n2].add((n1, w))
print(f'#{tc} {mst_prim(g, 0)}')
KRUSKAL 알고리즘
간선을 하나씩 선택해서 MST를 찾는 알고리즘
최초, 모든 간선을 가중치에 따라 오름차순 정렬
가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴
사이클이 존재하면 다음으로 가중치가 낮은 간선 선택
n-1 개의 간선이 선택될 때까지 위의 과정을 반복
알고리즘 적용 예시
알고리즘
# 크루스칼 알고리즘
# 대표원소 찾기
def find_set(x):
if x == _set[x]:
return x
else:
return find_set(_set[x])
# 두 개의 그룹을 하나로 묶기
def union(x, y):
_set[find_set(x)] = find_set(y)
def mst_kruskal():
mst = [] # 결과를 저장할 리스트 (추후에 간선과 가중치 정보가 필요할 때 사용)
res = 0 # 가중치의 합을 저장할 변수
while edge:
n1, n2, w = edge.pop() # 간선 정보를 호출
if find_set(n1) != find_set(n2): # n1과 n2의 대표원소가 같지 않을 경우 (Cycle 방지)
# mst.append((n1, n2, w))
union(n1, n2) # 하나의 set으로 병합
res += w # 해당 가중치를 누적합
# return mst
return res
for tc in range(1, int(input())+1):
v, e = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(e)]
edge.sort(key=lambda x: -x[2]) # 가중치 기준 오름차순 정렬
_set = [i for i in range(v+1)] # Make_set
res = mst_kruskal()
print(f'#{tc} {res}')
