Let IT Begin

* Python을 기준으로 합니다 신장 트리 (Spanning Tree) - 프림 / 크루스칼 알고리즘 - 개념 신장 트리 : 모든 노드와 연결되어 있으면서 사이클이 존재하지 않는 부분 그래프 이때 간선 개수는 노드의 개수 보다 하나 적음 최소 신장 트리 (Minimum Spanning Tree, MST) : 가중치 합이 최소인 신장 트리 - 이때 구해지는 최소 신장 트리는 여러 개일 수 있음 최소 신장 트리 구하기 공통적으로 그리디 전략을 이용하고, $E$개의 노드 $V$개의 간선에 대해 $O(E \log V)$의 time complexity를 가짐 프림 알고리즘 (Prim Algorithm) 임의의 노드를 선택하여 최소 신장 트리에 추가 최소 신장 트리와 연결되어 있는 노드 중에서 가장 가중치가 작은..