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

최소 신장 트리란(MinimumSpanningTree, MST)?

• 가중치가 있는 무방향의 그래프에서 최소 가중치의 간선으로 모든 정점(Vertex)를 연결하면서, 순환이 없어야한다.

• 요약하면 아래의 세 가지 특징을 갖는다.

  1. 모든 정점 연결
  2. 순환이 없음
  3. 최소 가중치

• 그림으로 표현하면 아래와 같다.

• 이를 구현하기 위한 대표적인 알고리즘 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 존재한다.