Algorithm. 그래프 - 최소 신장 트리

1. 그래프 최소 비용 문제 : 최소 신장 트리 문제 vs 최단 경로 문제

최소 신장 트리 문제

• 가중치 그래프에서 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리를 찾는 문제

최단 경로 문제

• 시작 정점에서 목표 정점까지 가는 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제

2. 신장 트리(Spanning Tree)

• 정점인 n개인 undirected graph에서 n개의 정점과 n-1개의 간선으로 구성된 트리
  • 즉, 모든 vertex set을 포함해야한다.
• 신장 트리의 수는 정점의 개수와 간선의 수의 비례한다.

3. 최소 신장 트리(Minimum Spanning Tree)

• 가중치 그래프의 신장 트리 중 간선들의 가중치의 합이 최소인 신장 트리
• 프림 알고리즘과 크루스칼 알고리즘이 존재한다.