MST1 최소 신장 트리 (MST , Minium Spanning Tree) 최소 신장 트리(MST, Minium Spanning Tree) 신장 트리 중에서 간선의 가중치의 합이 최소인 것 신장 트리(Spanning Tree) 그래프 내의 모든 정점을 연결한 트리 신장 트리의 특징 모든 노드는 서로 연결되어 있다. 간선(edge)의 수 E는 노드의 수 V에서 1을 뺀 것과 같다. 트리(Tree) 그래프의 일종으로 사이클이 없는 연결그래프이다. 트리의 특징 root node를 제외한 모든 node는 단 하나의 부모 node만 가진다. 임의의 노드에서 다른 노드로 가는 경로는 유일하다. 회로(cycle)가 존재하지 않는다. 간선(edge)를 하나 자르면 트리가 두 개로 분리된다. 최소 신장 트리 구현 방법 Kruskal 알고리즘 탐욕적인 방법(greedy method)을 이용해 M.. 2020. 5. 25. 이전 1 다음