거북목개발자

1. Minimum Spanning Tree : 각 간선이 갖고 있는 가중치의 합이 최소가 되는 신장 트리가 바로 최소 신장 트리이다. - Prim Algorithm 1) 그래프와 최소 신장 트리를 준비한다. 이때 최소 신장 트리는 노드가 하나도 없는 상태이다. 2) 그래프에서 임의의 정점을 시작 정점으로 선택하여 최소 신장 트리의 루트 노드로 삽입한다. 3) 최소 신장 트리에 삽입되어 있는 정점들과 이 정점들의 모든 인접 정점 사이에 있는 간선의 가중치를 조사한다. 간선 중에 가장 가중치가 작은 것을 골라 이 간선에 연결되어 있는 인접 정점을 최소 신장 트리에 삽입한다. 단, 새로 삽입되는 정점은 최소 신장 트리에 삽입 되어있는 기준의 노드들과 사이클을 형성해서는 안된다. 4) 3)의 과정을 반복하다가..