신장트리 최소비용 탐색
신장트리(spanning tree) 모든 정점을 포함하면서 사이클이 없는 트리 (트리의 조건) 목표 그리디(Prim, Kruskal) 알고리즘으로 mst(최소비용신장트리) 찾아보자 알고리즘의 최적의 여부를 검증해보자 그리디 알고리즘 결정 순간마다 가장 좋다고 생각되는 것을 해답으로 선택 선택은 그 당시(local)에는 최적이나 최종적인 선택(global)은 최적이라는 보장 없음, 검증 필수 Prim의 알고리즘 개념 집합에 속한 정점 중에서 가장 가까운 정점을 반복에서 추가하는 방법 처음 노드를 v1으로 선택했다고 하자 (랜덤으로 해도 상관없음) 순서 안보임 경계 결과집합 1 V4,V5 V2,V3 V1 2 V5 V3,V4 V1,V2 3 null V4,V5 V1,V2,V3 4 null V4 V1,V2,V3,..
