기본개념

1. spanning tree: 그래프 내에 모든 정점을 포함하는 트리
2. mst: spanning tree 중 edge 가중치 합이 최소인 트리
   1. 여러개의 mst 가질 수 있음

KRUSKAL’S ALGORITHM

1. greedy
2. 알고리즘
   1. 간선의 가중치 오름차순 정렬
   2. 정렬된 간선들을 탐색하며 해당 간선을 신장 트리에 포함할 때
      1. 사이클이 발생한 경우 신장 트리에 포함하지 않고 넘어감
      2. 사이클이 발생하지 않는 경우 신장 트리에 포함
   3. 모든 정점을 연결할 때까지 위 과정 반복
      

PRIM’S ALGORITHM

1. greedy
2. 알고리즘
   1. O(v^2)
   2. 최초 출발 노드와 연결되어 있는 간선들 중 가중치가 최소인 것을 선택해 MST에 추가
   3. MST에 포함된 모든 정점들과 연결된 간선들 중 가중치가 최소인 것을 선택해 MST에 추가
   4. V - 1개의 간선이 선택될 때까지 ②를 반복
      
   5. O(E log V) - 최소 힙 사용
      1. 임의 노드에서 시작
      2. edge 연결(가중치 최소인 edge로 연결), 연결된 node 값 수정
      3. 해당 tree에서 최소 node를 찾은 뒤, ② 반복
      4. 모든 vertex에서 진행 후 종료