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

그래프에서 최소 비용 문제

• 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
• 두 정점 사이의 최소 비용의 경로 찾기

신장트리

• Spanning Tree, 또는 신장 트리 라고 불리움
• 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프
• n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리
• 신장 트리의 조건
  • 본래의 그래프의 모든 노드를 포함해야 함
  • 모든 노드가 서로 연결
  • 트리의 속성을 만족시킴 (사이클이 존재하지 않음)

최소 신장 트리 (Minimum Spanning Tree)

• Minimum Spanning Tree, MST 라고 불리움
• 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭함
• 최소 신장트리 알고리즘
  • 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함
  • 대표적인 최소 신장 트리 알고리즘
    • Kruskal’s algorithm (크루스칼 알고리즘)
    • Prim's algorithm (프림 알고리즘)