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..
학부생 CS/자료구조
2019. 5. 30. 00:00