Data Structure : 최소비용신장트리 - Sollin's Algorithm (Boruvka's Algorithm)
Data Structure : 최소비용신장트리 - Sollin's Algorithm ( Boruvka's Algorithm ) Sollin의 알고리즘은 Greedy Strategy로, 각 스텝마다 가능한 최선의 선택지를 고르는 것을 반복하여 결과를 얻어낸다. 규칙 시작하면서 모든 정점을 Tree로 정의한다. ( Forest 상태 ) 하나의 Tree에 대해 외부의 Vertex와 연결 가능한 가장 비용이 작은 edge를 선택해 추가한다. edge가 중복되는 경우에는 하나만 추가한다. Tree가 하나로 이어질 때 까지 2를 반복한다. ( Forest 상태 X ) Sollin 알고리즘 모든 Vertex를 one-vertex Tree로 정의 while(tree가 하나가 아니면) { 모든 tree에 대해서 각각 T..
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 ) ..