수강한 강의 Chapter 20 그래프 고급 탐색 알고리즘 - 최소 신장 트리의 이해와 크루스칼 알고리즘 학습 후기 신장 트리(Spanning Tree)는 모든 노드들이 연결되어 있어야 하고 사이클을 포함해서는 안된다. n개의 노드로 이루어진 그래프는 n-1개의 간선으로 연결된다. 최소 신장 트리(Minimum Spanning Tree, MST) 최소 신장 트리는 Spanning Tree 중 1. 사용된 간선의 가중치 합이 최소이고 2. n개의 노드를 가지는 그래프에서 간선이 n-1개이고 3. 사이클이 포함되지 않은 트리이다. 크루스칼 알고리즘(Kruskal Algorithm) 그래프에서 최소 신장 트리(MST)를 찾는 알고리즘으로 탐욕 알고리즘에 기초하여 각 단계에서 사이클을 이루지 않는 최소 비용의 ..
