최소 신장 트리 (MST), Kruskal, Prim 알고리즘

우선 신장 트리 (Spanning Tree)는 n개의 정점으로 이루어진 그래프에서 n개의 정점n-1개의 간선으로 이루어진 그래프를 뜻한다.
즉 최소 간선개수로 모든 정점을 연결하는 트리를 말하는데, 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리를 최소 신장 트리 (Minimum Spanning Tree)라고 한다.

Pagination


© 2021. All rights reserved.

Powered by Hydejack v9.1.5