최소 신장 트리

신장 트리

개념

그래프 내의 모든 정점을 포함하는 트리

n개의 정점으로 이루어진 무방향 그래프에서 n-1개의 간선으로 이루어진 트리

 

특징

하나의 트리에는 다수의 신장트리가 존재할 수 있음

모든 정점들이 연결되어 있어야 하며, 싸이클을 포함해서는 안된다.

 

최소 신장 트리

개념

무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리

 

특징

가중치의 합이 최소여야 함

n개의 정점을 가지는 그래프에 대해 반드시 n-1개의 간선만을 사용해야함

사이클이 포함되면 안됨

 

활용

그래프에서 최소 비용을 구할때 활용

 

최소 신장 트리

 

 

※구현 방법

Prim 알고리즘

 

개념

하나의 정점에서 출발하여 연결된 간선들 중 하나씩 선택하면서 MST를 만들어나가는 방식

 

시간 복잡도

O(n^2)

 

특징

정점 선택 기반

이전의 mst에서 확장해 나감

 

방법

1. 임의의 정점을 하나 선택

2. 선택 정점과 인접 정점들 중 최소 비용의 간선으로 연결된 정점을 선택

3. 연결된 정점에서 다시 2번 수행

4. 모든 정점이 선택될 때까지 2,3번 과정을 반복

 

알고리즘

V,E = map(int,input().split())
adj = {i:[] for i in range(V)}
for i in range(E):
  s,e,c = map(int,input().split())
  adj[s].append([e,c])
  adj[e].append([s,c])
  
INF = float('inf')
cnt = 0
key = [INF]*V
mst = [False]*V
p = [-1]*V
p[0] = 0
mst[0] = True
key[0] = 0
u = 0
while cnt < V-1:
  for w,c in adj[u]:
    if not mst[w] and c < key[w]:
      key[w] = c
      p[w] = u
  min = INF
  for i in range(V):
    if key[i] < min:
      min = key[i]
      u = i
  cnt += 1

 

Prim 알고리즘

 

Kruscal 알고리즘

 

개념

탐욕적인 방법을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

 

시간 복잡도

O(elog₂e)

 

특징

간선 선택 기반

이전 단계에서 만들어진 신장트리와는 상관없이 무조건 최소 간선만을 선택

각 단계에서 사이클을 형성하지 않는 최소 비용의 간선 선택

 

방법

1. 간선 정보가 담긴 리스트에서 가중치를 기준으로 오름차순 정렬

2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 확장

3. 선택한 간선으로 인해 사이클이 생긴다면, 그 다음으로 낮은 가중치의 간선을 선택

4. 사이클의 여부는 서로소 집합을 이용해서 정점의 대표자가 같으면 사이클이 발생한 것으로 간주

5. n-1개의 간선이 선택될 때까지 위 과정을 반복

 

알고리즘

def make_set(x):
  p[x] = x
  
def find_set(x):
  if x == p[x]:
    return x
  else:
    p[x] = find_set(p[x])
    return p[x]
  
def union(x,y):
  px = find_set(x)
  py = find_set(y)
  if rank[px] > rank[py]:
    p[py] = px
  else:
    p[px] = py
    if p[px] == p[py]:
      rank[py] += 1
  #union이 끝나면 흡수된 트리의 종속되어있는 자식들의 대표자도 흡수한 노드로 바꿔줘야하기 때문에 find_set으로 한번 씩 돌림
  for i in range(V):
    find_set(i)
    

V,E = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(E)]
#간선을 간선 가중치를 기준으로 정렬
edges.sort(key=lambda x:x[2]) #x를 넣으면 x[2]를 반환

#make_set : 모든 정점에 대해 집합 생성
p = [0]*V
rank = [0]*V
for i in range(V):
  make_set(i)

cnt = result = 0
mst = []
#모든 간선에 대해서 반복 -> V-1개의 간선이 선택될 때까지(모든 정점이 연결되려면 간선의 갯수는 V-1개여야하므로)
for i in range(E):
  s,e,c = edges[i][0],edges[i][1],edges[i][2]
  #사이클이면 스킵 : 간선의 두 정점이 서로 같은 집합이면 => find_set
  if finde_set(s) == find_set(e): continue
  #간선 선택
	#=> mst에 간선 정보 더하기 / 두 정점을 합친다 => union
  result += c
  mst.append(edges[i])
  union(s,e)
  cnt += 1
  if cnt == V-1: break #간선을 V-1개 선택했으면 종료

 

Kruscal 알고리즘

 

※Prim vs Krucal

Prim: 간선이 많은 밀집 그래프에 적합

Kruscal: 간선의 수가 적은 희소 그래프에 적합

최단경로

개념

간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로

 

※분류

하나의 시작 정점에서 끝 정점까지의 최단경로

- 다익스트라 알고리즘: 음의 가중치 허용 x

- 벨만-포드 알고리즘: 음의 가중치 허용

모든 정점들에 대한 최단 경로

- 플로이드-워샬 알고리즘

 

다익스트라 알고리즘

 

특징

시작 정점에서 거리가 최소인 정점 선택해 나감

탐욕 기법을 사용

MST의 프림 알고리즘과 유사

 

알고리즘

#다익스트라 + 인접리스트
V,E = map(int,input().split())
adj = {i:[] for i in range(V)}
for i in range(E):
  s,e,c = map(int, input().split())
  adj[s].append([e,c])
INF=float('inf')
#dist, selected 배열 준비
dist = [INF]*V
selected = [False]*V

dist[0] = 0 #시작점 선택 
cnt = 0
while cnt < V: #모든 정점이 선택될때까지 
  #dist가 최소인 정점 찾기
  min = INF
  for i in range(V):
    if not selected[i] and dist[i]<min:
      min = dist[i]
      u = i #아직 선택되지 않고 dist의 값이 최소인 정점: u
  #정점 u의 최단거리 결정
  selected[u] = True
  cnt += 1
  #정점 u에 인접한 정점에 대해서 간선완화
  for w,cost in adj[u]: #도착 정점, 가중치
  	if dist[u]+cost < dist[w]:
      dist[w] = dist[u]+cost
print(dist)

 

참고

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html