최소 신장 트리(MST)란?최소 신장 트리(Minimum Spanning Tree)를 알기 위해서는 신장 트리(Spanning Tree)가 무엇인지 알아야 한다. 신장 트리(Spanning Tree)위의 그림 그래프에서 아래 그래프 3개 모두 신장 트리(위 그림에 따르면 3개가 더 존재함.)그래프의 모든 정점을 포함하는 트리그래프의 최소 연결 부분 그래프로 사이클이 없음정점의 개수 n개면 간선의 개수 n-1개 가짐(사이클이 존재하지 않기 때문이다.)하나의 그래프에 많은 신장 트리 존재최소 신장 트리(Minimum Spanning Tree)가운데 신장 트리는 신장 트리 중 가중치 합이 가장 최소인 최소 신장 트리신장 트리 중 간선의 가중치 합이 최소인 트리사이클이 없는 그래프 중 최소의 가중치크루스칼(kr..
