📒 코테연습장/📝 트리

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

신장 트리 (Spanning Tree) 무방향 그래프의 최소 연결 부분 그래프를 말한다. 즉, N개의 정점을 가지는 그래프 중 모든 정점을 포함하면서 최소 간선의 수인 N-1개의 간선으로 연결된 부분 그래프를 뜻한다. 특정 그래프에서 최소 간선 수인 N-1개의 간선을 가지고 있는 그래프는 트리 형태를 이룰 수 밖에 없어 신장 "트리"라고 한다. 🔹정점 수: N 🔹간선 수: N-1 🔹즉, 그래프 내 모든 정점을 포함하는 트리 (사이클 존재 X) 위의 그림과 같이 하나의 그래프에서 신장 트리는 여러개가 존재할 수 있다. 이때 하나의 그래프에서 생성될 수 있는 신장 트리 중 가중치의 합이 가장 작은 트리를 최소 신장 트리라고 한다. MST를 구할 수 있는 알고리즘으로 크루스칼 알고리즘과 프림 알고리즘이 있다...