[Data Structure] 최소 신장 트리 - Kruskal MST Algorithm

신장 트리 (Spanning Tree) - 그래프의 모든 정점들을 포함하는 트리 - 모든 정점들이 연결되어 있어야 하고, 사이클을 포함하면 안된다 최소 신장 트리 (Minimum Spanning Tree) - 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장트리 - 모든 정점들을 가장 적은 수의 간선, 비용으로 연결 - n개의 정점들에 대해 반드시 n-1개의 간선만 사용 + 사이클 포함 X ex) 도로 건설, 전기 회로, 통신, 배관,.... Kruskal Algorithm, Prim Algorithm Kruskal MST Algorithm - 탐욕적 방법 (greedy method) 이용 - 간선을 기반으로 하는 알고리즘 - 간선의 개수 e개 → O(|e|log₂|e|) - 매 선택마다 최선의..

2021.12.24