[알고리즘] 최소신장트리, MST, 크루스칼/프림 알고리즘

_Spanning Tree 정의

Spanning Tree(신장트리)는 아래의 속성을 만족하는 그래프를 말한다.

• 원래의 그래프의 모든 노드를 포함
• 모든 노드가 서로 연결되어 있음
• 트리의 속성을 만족 ( 사이클이 존재하지 않음)

즉, 그래프의 최소 연결 부분 그래프이다.

• 최소 연결 = 간선의 수가 가장 적다
• N개의 노드를 가진 그래프
  • 최소 간선의 수 : N-1
  • (N-1)개의 간선으로 == 최소 간선으로 연결되어 있으며 트리의 형태이면 Spanning Tree

 

_Minimum Spanning Tree (MST)

가능한 Spanning Tree 중에서 간선의 가중치 합이 최소인 Spanning Tree

출처 : 위키백과

위 사진에서 첫 번째 그래프의 경우 2개의 MST를 가질 수 있다.

두번째, 세번째 트리가 모두 가중치의 합이 최소이기 때문에 최소신장트리의 조건을 만족한다.

 

_MST 구현방법

그래프에서 MST(최소 신장 트리)를 찾을 수 있는 알고리즘

• Kruskal's algorithm (크루스칼 알고리즘)
• Prim's algorithm (프림 알고리즘)