prim (1) 썸네일형 리스트형 [알고리즘] 최소 신장 트리(Minimum Spanning Tree / MST) 개요 및 개념 임의의 정점(Vertex or Node)에서 다른 정점으로 연결된 모든 간선(Edge)들이 가중치를 가졌을 때, 모든 정점을 연결한 가장 적은 가중치의 합을 가지는 트리(Tree)를 만들려면 어떻게 해야할까요? 트리(Tree)란 순환(Cycle)을 가지지 않는 연결 그래프이며 임의의 두 정점에 대해 경로는 반드시 1개만 존재합니다. 최소 신장 트리(MST)란? 신장 트리(Spanning Tree)는 무향 연결 그래프 G가 있을때, G의 부분 그래프이며, G의 모든 정점을 포함하는 트리(Tree) 구조인 그래프라고 할 수 있습니다. 위 그림과 같이 무향 그래프 G의 모든 정점을 포함하는 트리를 신장트리, Spanning Tree 라고 합니다. 그리고 만약 여기서 간선들이 가중치를 가졌다면 가중치의 합을 최.. 이전 1 다음
