목록MST (1)

munjji 님의 블로그

[알고리즘] 최소 신장 트리 (MST) (feat. kruskal, Prim 알고리즘)

최소 신장 트리 (MST: Minimum Spanning Tree)그래프에서 모든 정점을 포함하고 사이클이 없으며, 총 간선 비용이 최소인 트리MST의 핵심 특징간선은 정확히 n - 1개사이클이 없음모든 노드 연결총 비용 최소 MST를 구하는 대표 알고리즘 2개알고리즘의 공동목표모든 정점을 최소 비용으로 사이클 없이 연결하자즉, 최소 신장 트리 만들기1️⃣ Kruskal 알고리즘"간선을 비용 기준으로 정렬해서 가장 싼 것부터 고르자"간선 비용(cost) 기준 오름차순 정렬작은 것부터 선택사이클 생기면 건너뜀Union - Find 사용시간복잡도는 O(E log E)과정모든 간선을 비용 기준 오름차순 정렬가장 작은 간선부터 하나씩 선택사이클이 생기면 버림간선이 V-1개가 되면 종료2️⃣ Prim 알고리즘"현..
알고리즘 2026. 2. 25. 17:21
이전 Prev 1 Next 다음