Study/Algorithm
-
Kruskal's algorithm : 최소 신장 트리(MST, Minimum Spanning Tree) 찾기Study/Algorithm 2023. 8. 31. 16:30
BOJ 문제 최소 스패닝 트리(1197), 도시 분할 계획(1647), 네트워크 연결(1922) 등의 문제들을 풀기 위해 Kruskal Algorithm을 공부했다. 1. 알고리즘 최소 신장 트리(MST, Minimum Spanning Tree)는 가중치(weight)가 있는 간선(edge)들을 갖고 있는 그래프에서, 그래프의 모든 정점(vertex)들을 포함한 트리(tree)이면서, 그 트리가 가진 모든 간선의 가중치의 합이 가장 작게 되는 그래프를 말한다. 예를 들면, 아래의 그래프 G에서 모든 정점을 포함한 트리는 가운데의 그래프에서 빨간 간선들로 이루어진 그래프이고, 그러한 트리는 여러 개가 있을 수 있다.(모든 정점을 포함한 트리를 spanning tree라고 한다.) 하지만, 간선의 가중치의 ..