[그래프] 신장트리 7/5

* 신장 트리
 - 기존 그래프의 모든 노드를 포함
 - 순환이 존재하지 않는 부분 그래프
  > 신장트리도 트리의 일종이므로 순환이 존재하면 안된다.
 - 그래프 탐색을 통해 생성 가능

* 최소비용 신장 트리
 - 그래프에서 모든 노드를 방문할 때 가중치의 합이 가장 적은 신장트리
 ⓐ Kruskal 알고리즘
  - 모든 간선을 가중치 순으로 정렬하여 초기화
  - 낮은 가중치를 가지는 간선을 선택하여 트리를 완성
    (단, 간선 선택시 순환이 발생하면 안된다.)

  ex)

1) 초기화 (가중치에 의한 오름차순 정렬)
 간선   /   가중치
 (1,2)   /      1
 (2,5)   /      2
 (2,3)   /      3
 (3,5)   /      4
 (1,4)   /      5
 (4,5)   /      6


 2) 낮은 가중치의 간선을 차례대로 선택, 이때 순환이 발생하면 안된다.

 ⓑ Prim 알고리즘
  - 임의의 시장 노드 1개를 지정 후 알고리즘 시작
  - 현재 선택되 있는 노드에서 발생되는 모든 간선(연결될 간선/부속되있는 간선) 중 비용이 가장적은 간선선택

  ex)

1) ①노드<시작노드 선택>
2) (1, 2) vs (1, 4) 가중치 1인 (1, 4)선택
3) (1, 4) vs (2, 3) vs (2, 5) 가중치 2인 (2, 5)선택
4) (1, 4) vs (2, 3) vs (3, 5) vs (4, 5) 가중치 3인 (2, 3)선택
5) (1, 4) vs (3, 5) vs (4, 5) 가중치 4인 (3, 5)선택
    But, 순환 발생, 다음 가중치를 가지는 (1, 4)선택
6) 그래프의 모든 노드 선택완료, 알고리즘 종료