MST
MST (최소 신장 트리)
-
- 신장 트리??
- 어떤 그래프 안에 있는 모든 노드를 연결하는 트리
그래프 안에 있는 변만을 사용
신장 트리는 여럿 있을 수 있음
- 신장 트리??
-
- 최소 신장 트리
- 신장 트리 중 ‘비용’이 최소인 트리
(비용 : 모든 변의 가중치를 합한 값)
(최소 ‘비용’ 신장 트리 라고도 함)
- 최소 신장 트리
-
최소 신장 트리에서 ‘간선의 개수?’ : N -1 개
-
순환 : ‘반복되는 노드가 시작 노드 끝 노드 뿐인 경로’
-
컷 : 어떤 그래프를 서로소(disJoint)인 두 하위 집합
으로 나누는 행위
‘그래프의 노드’ 들을 두 그룹으로 분리시키는 것
컷 세트 (cut - set) : 두 그룹을 연결하는 간선들의 집합
-> 이 간선들을 제거하면 그래프가 둘로 분리됨 - 컷 프로퍼티(cut property)
컷 세트에 가중치가 다른 여러 간선이 있는 경우,
(가중 그래프임을 가정)
MST에 포함되는 간선은 가장 가중치가 작은 간선
MST 의 기본 원리
- 그래프에 있는 노드 중 한 변을 확인
- 이 변이 MST에 들어가야 하는지 검사
이 때, cut property를 사용
들어가야 하면 MST에 추가, 아니면 무시 - MST의 모든 변을 찾지 못했다면 1로 돌아감
- Greedy 알고리즘
MST 알고리즘의 예시
- Kruskal’s Algorithm
- 그래프의 각 노드마다 그 노드만 포함하는 트리를 만듦
- 모든 간선의 가중치의 오름차순 정렬 => S 배열
(정확히는 각 간선이 ‘무엇’과 ‘무엇’을 가리키는지도 필요) - S가 비거나 MST가 완성될 때까지 다음을 반복
1) S에서 가중치가 가장 적은 간선을 제거해서 고려 2) 이 간선이 두 트리를 연결하는지 검사
=> 그렇다면 MST에 추가
아니라면 버림
(두 트리를 연결하는지 검사하는 데 필요한 것이
‘서로소집합’ 자료구조)
- 시간복잡도 : O(E Log E) (변 정렬)
+ 서로소집합 시간 복잡도
(약 O(E Log V))
- Prim’s Algorithm
- 아무 노드 하나 골라 트리를 만듦
- 이 트리를 성장시킬 수 있는 간선을 하나 고름
아직 트리에 속하지 않은 노드와 연결하는 간선 중
비용이 가장 적은 간선
이미 트리에 속해있는 노드와 연결하는 변이면 무시 - MST가 완성되거나 고려할 변이 없을때까지 2번 반복!
(다익스트라와 유사한 느낌)
- 아무 노드 하나 골라 트리를 만듦
유니온 - 파인드 (서로소집합 자료구조)
겹치지 않는 ‘집합’들을 저장하는 자료 구조
서로 다른 트리는 ‘겹치지 않는’ 집합
이걸 서로소 집합에 저장하면 간단한 연산만으로
겹치는지 파악 가능
Union-Find, disjoint-set 등으로 불림
- 연산 방법
- MakeSet(element) : 새로운 집합 생성
(새로운 요소 여야 한다) - Find(element) : element가 속한 집합을 찾음
ex) find(x) != find(y) : 둘은 다른 집합!
가장 간단한 구현은 ‘집합’에 속한 요소 중 하나를
결정론적으로 반환 - Union(element1,element2) : 두 집합을 합침
element1 이 속한 집합 + element2 가 속한 집합
- MakeSet(element) : 새로운 집합 생성
- 크러스컬 알고리즘 적용방식
- 그래프에 있는 각 노드 N에 대해 MakeSet(N)
- 모든 변을 가중치의 오름차순으로 정렬(S 배열)
- S가 비거나 MST가 완성될 때까지 다음의 과정 반복
1) S에서 가중치가 가장 적은 간선을 제거 2) 이 간선이 연결하는 두 노드 u,v에 대해
Find(u) != Find(v) 라면
Union(u,v)
이 변을 MST에 추가하기
- 그래프에 있는 각 노드 N에 대해 MakeSet(N)
코드 예시 (Python)
크루스칼 알고리즘 + 서로소집합 (백준 1197)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
result = 0
V,E = map(int,input().split())
G = []
for i in range(E):
edgeData = list(map(int,input().split()))
# 저장 방식을 '가중치 , a, b' 로 바꿈
edgeData[0],edgeData[1],edgeData[2] = edgeData[2],edgeData[0],edgeData[1]
G.append(edgeData)
# 정렬 조건없이 바로 돌린다 (가중치 기준 오름차순)
# 아니면 위에서 저렇게 값 순서를 바꿔주지 않고
# G.sort(key=lambda x : x[2]) 해도 된다
G.sort()
# 각 노드의 부모를 저장할 배열
parent = [i for i in range(V)]
# union-find
# 부모 구해주기
def getParent(node : int)->int:
if parent[node] == node:
return node
parent[node] = getParent(parent[node])
return parent[node]
# 부모 합쳐주기
def unionParent(a : int, b : int):
aP = getParent(a)
bP = getParent(b)
if aP < bP :
parent[bP] = aP
else:
parent[aP] = bP
# 두 부모가 같은지 확인
def checkSameParent(a:int,b:int)->bool:
aP = getParent(a)
bP = getParent(b)
if aP == bP:
return True
else:
return False
# 낮은 가중치를 가진 G 부터 들어가게 됨
for i in G:
# 같은 부모를 가지고 있다면 무시하고,
# 다르다면 아직 연결하지 않은 것이므로 합쳐준다
if checkSameParent(i[1]-1,i[2]-1) == False:
unionParent(i[1]-1,i[2]-1)
result += i[0]
# 이건 '합'을 구하는것
# 연결방식을 보여주는 방식의 경우엔,
# node를 따로 저장할 방법
print(result)
프림 알고리즘(마찬가지로 백준 1197)
import heapq
import collections
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m = map(int,input().split()) # 노드 수, 간선 수
graph = collections.defaultdict(list) # 빈 그래프 생성 (딕셔너리 [key,list])
visited = [False] * (n) # 노드의 방문 정보 초기화
# 무방향 그래프
for i in range(m): # 간선 정보 입력 받기
start, to, cost = map(int,input().split())
graph[start].append([cost, start, to])
graph[to].append([cost, to, start])
def prims(graph,start_node):
visited[start_node-1] = True
edges = graph[start_node]
heapq.heapify(edges)# 우선순위 큐(최소 힙 이며, 첫 요소가 cost이기에 오름차순정렬)
mst = [] # mst (경로)
total_cost = 0 # 전체 가중치
while edges:
cost, start, to = heapq.heappop(edges)
if visited[to-1] == False:
visited[to-1] = True
mst.append((start,to))
total_cost += cost
for nextEdge in graph[to]:
if visited[nextEdge[2] - 1] == False : # 방문한 노드 아님
heapq.heappush(edges,nextEdge)
return total_cost
print(prims(graph,1))
댓글남기기