최소 신장 트리(MST)

DAG

방향 비순환 그래프

u가 v보다 먼저 오도록 하는 정렬 기법

• 비순환 그래프여야한다.

1. 진입차수
2. 진출차수

트라이

최소신장트리

간선: 노드-1

간선 가중치의 합이 최소인 트리

1. 크루스칼 간선 가중치 기준 정렬 union find: 부모를 찾아서 같으면 합치지 않고(사이클 x), 같지 않으면 합침 (사이클 o)

2. 프림