Prim's Algorithm

• Minimum Spanning Tree (MST) - 최소 신장 트리
• 정점 기준
  • 정점의 인접 간선을 통해 확장해 가는 방식 - Greedy
  • 현재 관점 시점
    • 현재 정점에 의한 간선들만 아니까
• 로직
  • 시작 정점 선택, 인접 간선 리스트에서 해당 정점 간선을 후보 간선 리스트에 추가
  • 후보 간선중 최소 간선 선택, 해당 정점 연결
    • 이미 해당 정점이 포함되어 있으면 무시 (해당 간선 pass)
  • 연결된 정점의 인접 간선도 후보 간선 리스트에 추가
  • 노드 - 1 개의 간선이 포함되면 종료 or 간선 다 순회
    • 후보 간선 리스트가 비어 있으면 종료
• 초기 값
  • 인접 간선 리스트
    • 선택된 정점의 간선을 가져와 후보 간선 리스트에 넣는 용
  • 후보 인접 간선 리스트
    • priority_queue, heap으로 구성
  • 연결 확인용 자료
    • set으로 현재 MST 노드들 확인
  • 아무 노드를 시작 정점, 해당 정점의 인접 간선들 후보리스트에 추가
  • 후보리스트가 빌때까지 수행 while
• $E\log E$
  • 큐에서 가장 최악
• 개선된 프림 알고리즘
  • 정점이 간선보다 수가 적으므로 정점을 기준으로 우선순위 큐
  • 간선의 최소값이 아닌 노드의 최소값을 중심으로 우선순위 큐를 적용하는 방식
  • 로직
    • 최초 노드의 간선 값을 해당 간선 노드들의 값으로 부여, 큐에 넣기
    • 큐에서 최소값 노드를 가져와 간선 값과, 노드값 비교 업데이트
      • (무한대에서) 업데이트된 새로운 노드 큐에 넣기
      • 이미 큐에 있는 노드는?
        • 큐에 있는 값을 업데이트 해야하는 상황이 존재
          • 다익스트라처럼 현재 값 리스트가 있고, 다르면 무시하는 방향으로
    • 큐가 빌때까지
  • $E\log V$
    • 큐에서 가장 최악
    • 정점($V$)이 간선($E$)보다 최소 1개라도 적으므로 개선
    • $E>V$, 최악의 경우 $V^2=E$