최소신장 트리 최소 신장 트리(Maximum Spanning Tree, MST)란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리입니다. 아래 특징을 가집니다. 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음. N 개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1 개임. 최소 신장 트리 핵심 이론 1. 그래프 구현(에지 리스트), 유니온 파인드 배열 초기화 최소 신장 트리는 데이터를 노드가 아니라 에지를 중심으로 저장합니다. 그래서 벨만-포드 알고리즘에서처럼 에지 리스트의 형태로 저장해야 합니다. Edge 클래스는 일반적으로 노드 변수 2개, 가중치 변수 1개로 구성됩니다. 사이클 처리를 위한 유니온 파인드 배열도 초..
