kruskal

[알고리즘] 최소 신장 트리(MST) - Kruskal, Prim, Sollin 알고리즘

최소 신장 트리(Minimum Spanning Tree, MST)이란? 최소 신장 트리를 배우기 앞서, 신장 트리란 무엇인지 알아야 한다. 이는 연결 그래프의 부분 그래프로, 모든 정점과 간선의 부분집합으로 구성된다. 신장 트리의 중요한 특징 중 하나는 모든 노드가 적어도 하나의 간선과 정점에 연결되어야 하며, 사이클을 만들면 안된다. 최소 신장 트리를 이해하기 위해서는 이러한 신정트리의 개념을 정확히 파악하고 있어야 한다. 아래와 같은 그래프가 신장 트리의 예시 중 하나이다. 최소 신장 트리는 하나의 연결 성분으로 이루어진 무방향 가중치 그래프에서 간선의 가중치의 합이 최소인 신장트리를 말한다. 이러한 최소 신장 트리 알고리즘은 대표적으로 Kruskal, Prim, Sollin 알고리즘이 있다. 이는 ..