최소 신장 트리

개요 MST (Minimum Spanning Tree)를 구하는 알고리즘 what's MST? 모든 노드(Vertex)를 최소 비용으로 최소 간선(Edge)을 사용해 연결한 트리 (no cycle) * MST의 Edge수는 Number Of Vertex - 1 이다. Where to use MST? Network Design Approximation algorithms (ex. traveling salesperson problem) When to use Kruskal Get MST of undirected graph by Greedy algorithm Algorithm (1) Sort all edges in ordering by weight (ascending) => 최소 비용 간선 오름차순 (2) Pi..