최소 스패닝 트리 - MST (크루스칼 알고리즘)

반갑습니다.

 

오늘은 최소 스패닝 트리 MST(Minimum Spanning Tree)에 대해서 공부해보겠습니다.

MST ( Minimum Spanning Tree ) 란?

기존의 그래프에서 신장 트리를 구성할 때 그 간선의 가중치 합이 제일 작은 신장 트 

• 모든 정점이 연결되어있다.
• 간선의 갯수는 정점의 갯수에 -1을 한 것이다.
• 간선에 가중치가 존재한다.
• 트리 이기 때문에 사이클이 존재하지 않는다.