차곡차곡.

먼저, 신장트리(Spanning Tree)란 방향성이 없는 N개 정점의 가중치 그래프에서 모든 정점을 연결하는 N-1개의 간선으로 구성된 트리를 말한다. 즉, 최소신장트리(MST: Minimum Spanning Tree)는 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 신장트리를 찾는 것이다. MST를 구할 때 대표적으로 쓰이는 프림(Prim), 크루스칼(Kruskal) 알고리즘에 대해 알아보자. 프림(Prim) : 정점을 선택/미선택 집합으로 구별하고, 선택된 정점 미선택된 정점 사이의 간선 중 가장 작은 간선을 택하면서 정점을 연결해나가는 방법의 풀이이다. => 정점 중심 풀이 [풀이 순서] 1. 임의의 정점을 하나 선택. 2. 선택된 정점들로부터 인접한 아직 선택되지 않은 정점까지의 가장 ..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 더보기 문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의..