Data Structure : 최소비용신장트리 - Prim's Algorithm
Data Structure : 최소비용신장트리 - Prim's Algorithm Prim의 알고리즘은 Greedy Strategy로, 각 스텝마다 가능한 최선의 선택지를 고르는 것을 반복하여 결과를 얻어낸다. 규칙 하나의 정점에서 시작함. 한번에 하나씩 Tree에 간선을 추가하고, 추가한 결과는 Tree를 이루어야 한다. Tree가 여러 개이면 Forest Tree에 추가한 간선이 Cycle을 구성하지 않도록, 간선을 고를 때 Tree에 속해있는 Vertex 하나와 속하지 않은 Vertex 하나가 만드는 간선을 골라야 한다. Tree에 속한 edge의 개수가 vertex 개수 - 1인 경우 ( Spanning Tree 조건을 만족 ) 또는 추가할 edge가 없는 경우 ( Spanning Tree X ) ..
학부생 CS/자료구조
2019. 5. 29. 16:46