[자료구조] 최소 신장 트리와 크루스칼 알고리즘

최소 신장 트리란?

신장 트리 (Spanning Tree) :

• 그래프 상에서 모든 노드가 사이클이 없이 연결된 부분 그래프를 뜻한다.

가중치 (Weight) : 노드와 노드 사이에 간선을 연결할때의 드는 비용. Coast 라고도 불리운다.

• 가중치는 거리, 비용, 시간 등 상황에 맞게 부여된다.

최소 신장 트리 (Maximum Spanning Tree) :

• 여러개의 부분 그래프 중에 모든 정점이 Coast의 최저합으로 연결된 부분 그래프를 의미한다.
• 노드를 연결할수 있는 모든 경우의 수중에 신장트리 + 모든 간선의 가중치의 합이 최소

• Spanning Tree : 모든 노드가 선으로 연결됨