[알고리즘] 최소신장트리(MST)

❔ 최소 신장 트리(MST)란? ❔

< MST : Minimum Spanning Tree>

• 신장 트리 중 가중치의 합이 최소가 되는 신장트리
• 여러개가 존재할 수도 있다.
• 경로 연결간에 가장 저렴한 경로를 찾는데 사용
• 순환되면 안된다
• MST의 간선의 개수 = n - 1
• 탐욕법(Greedy) 알고리즘 중 하나

탐욕법 (Greedy)

• 구성 : 다양한 선택, 모음, 또는 찾아야 할 값들

• 목표 : 구성에 할당된 점수가 존재하며 , 이를 최대화 또는 최소화 해야하는 상황

• 탐욕적 선택 속성
  => 출발 구성으로부터 시작하여 지속적인 지역적 향상을 통해 전체 최적해를 찾을 수있는 경우 사용

  ex) 잔돈 거스르기 문제 => 가능한 항상 제일 큰 동전으로 거슬러 준다

  • 동전 종류 (32,8,1) => O
  • 동전 종류 (30,20,5) => X
    => 탐욕적 선택 속성 없음 => 40원은 2개의 20원으로 가능하지만 30원 1개, 5원 2개를 하게 될것

Prim-Jarnik 알고리즘

• 대상 : 단순 연결 무방향 가중 그래프
• 임의의 정점 s를 택하여 s로부터 시작하여, 현 단계에서 갈 수 있는 모든 곳을 검색해 가장 저렴한 곳 연결 (순환이 되면 X)
• n개의 노드를 채울때까지 반복
• 우선 순위 큐 (이진 힙)이용

<핵심>

트리에 속하지 않은 정점들 중
트리에 인접한 간선에서
최소의 가중치를 갖는 간선을 선택한다는 것이다.

visited 리스트를 이용하여 처리
정점이 트리에 속해질 때마다 정점의 인접 간선 정보 업데이트