Prim algorithm

1. 정점 하나를 가진 트리에서 시작
   • TV = {v1}
     • TV : 트리의 정점
2. 트리 내의 정점 u와 트리 밖의 정점 v를 잇는 Edge 중 최소 비용을 가진 (u,v)를 트리 Edge로 만든다.
   • TE = TV U {u,v}
3. 트리 밖의 정점 v도 트리의 정점으로 만든다.
   • TV = TV U {v}
4. TV = V(G)와 같아지면 종료

Kruskal algorithm

1. Edge를 가중치가 작은 것에서 큰 것 순으로 정렬
2. 트리에 Edge를 하나씩 추가
3. 사이클이 생기면 추가하지 않는다.
4. 최소 비용 신장 트리가 완성되면 |E| = |v|-1

MST(Minimum cost Spanning Tree)

신장 트리(Spanning Tree)

1. connected(연결되어 있다.)
2. 최소 엣지 수 |E| = |V| - 1 (트리 조건)
3. E(G’)는 E(G)에 포함되어 있다.
4. V(G’) = V(G)

최소 비용 신장 트리

1. 무방향 그래프
2. 가중치 그래프
3. 비용(cost) 최소화