[알고리즘/C++] 크루스칼 알고리즘(Kruskal Algorithm)

최소 신장 트리(Minimum spanning Tree)는 그래프 내에서 1.사이클을 생성하지 않으면서 2.그래프의 모든 노드를 포함하는 3. 최소 가중치 합의 간선을 갖는 부분 그래프 를 의미한다. 이러한 최소 신장 트리를 찾는 알고리즘이 바로 크루스칼(Kruskal) 알고리즘이다. 크루스칼 알고리즘은 기본적으로 탐욕 알고리즘의 일종으로서 가장 짧은 간선(edge)를 찾고 이를 트리에 추가함으로써 최소 신장 트리를 만들어낸다. 출처: https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/ 크루스칼 알고리즘의 주요 메커니즘은 다음과 같다. 1. 그래프에서 가장 짧은 간선(Edge)를 찾는다. 2. 해당 간..

2023.08.04