MST

🌲 최소 신장 트리(MST-Minimum Spanning Tree)란?정의: 무방향 가중치 그래프에서 모든 정점을 연결하면서 간선 가중치의 합이 최소가 되는 트리를 의미합니다.조건모든 정점이 연결되어 있어야 함 (연결 그래프)사이클이 없어야 함 (트리 구조)정점의 갯수가 V인 그래프의 최소 신장 트리는 V-1개의 간선을 가진다.📌 크루스칼 알고리즘 (Kruskal's Algorithm)🔧 핵심 아이디어"간선을 하나씩 가중치가 작은 순으로 선택하되, 사이클을 만들지 않도록 유니온-파인드(Disjoint Set)를 이용해서 연결한다."🪜 동작 순서간선을 가중치 기준으로 오름차순 정렬한다.가장 가중치가 낮은 간선부터 하나씩 선택한다.선택한 두 정점이 **서로 다른 집합(사이클 X)**이면 연결한다.모든..