최소 신장 트리(Minimum Spannig Tree)

• 신장 트리중 가중치의 합이 최소인 신장트리
• 크루스칼 알고리즘
  • 간선 선택 기반 알고리즘
  • 동작
    • 모든 간선을 가중치로 오름차순 정렬
    • 정렬된 간선에서 사이클이 형성되지 않도록 간선을 선택
      • 오름차순으로 되어 있으므로 작은 것부터 먼저 선택하게 됨 
      • 사이클이 형성되는 간선은 제외
    • 선택한 정점을 MST 집합에 포함
    • 간선의 개수가 n-1개가 될때까지 수행
  • Union-Find 알고리즘으로 사이클 형성 확인
• 프림 알고리즘
  • 정점 선택 기반 알고리즘
  • 동작
    • 시작 정점을 MST 집합에 포함
    • MST 집합에 연결된 정점 중 아직 방문하지 않았고 가중치가 가장 작은 간선 선택
      • 가장 낮은 가중치를 먼저 선택
    • 선택한 간선으로 연결된 정점 MST 집합에 포함
    • 간선의 개수가 n-1개가 될때까지 수행
  • 우선순위 큐로 구현
  • 다익스트라와의 차이
    • 다익스트라는 한정점에서 한정점까지 가중치의 합이 가장 작은 것으로 연결
    • 프림은 한정점과 한정점의 가중치의 합이 가장 작은것이 아닐 수도 있음