최소 신장 트리

최소 신장 트리(minimum spanning tree)그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.주요 특징사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.N 개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1개다.핵심 이론 백준 1197번 : 최소 스패닝 트리https://www.acmicpc.net/problem/1197 #include #include #include #include using namespace std;// 0: 가중치 / 1 : 시작 노드 / 2 : 도착 노드typedef tuple Edge;int V, E;vector parent; //union find 배열void Union(i..

2025.01.26