본문내용
이루지 않으므로, 표시된다. ④cd는 기존의 변들과 회로를 이루지 않으므로, 표시된다. bd는 bcd 회로를 이루게 되므로 삭제하고, be는 기존의 변들과 bce회로를 이루므로 표시되지 않는다. 마지막으로, ⑤df가 기존의 변들과 회로를 이루지 않으므로 표시된다. 이 때의 최소신장트리에서 가중치의 합은, 1+1+2+2+7=13이다.
6. 초기 S={a}에서, a와 연결된 변 ab(2), ac(1) 중 가중치가 낮은 변 ac(1)을 선택한다. S={a,c}가 되었으므로, c와 연결된 변 cb(3), ce(3), cd(1) 중, 가중지가 낮은 변 cd(1)을 선택한다. S={a, c, d}가 되었으므로, d와 연결된 변 de(2), df(3), db(5) 중에서 가중치가 낮은 변 de(2)를 선택한다. S={a, c, d, e}가 되었으므로, e와 연결된 변 ef(2), eb(2) 중에서 ef(2)를 선택한다. S={a, c, d, e, f}에서 f와 변으로 연결된 점은 V={b} 중에 없으므로, 다시 e와 연결된 변 eb(2)를 선택한다. S={a, c, d, e, f, b}가 되고, 프림 알고리즘은 종료된다. 이 때 가중치는 1+1+2+2+2=8이다.
6. 초기 S={a}에서, a와 연결된 변 ab(2), ac(1) 중 가중치가 낮은 변 ac(1)을 선택한다. S={a,c}가 되었으므로, c와 연결된 변 cb(3), ce(3), cd(1) 중, 가중지가 낮은 변 cd(1)을 선택한다. S={a, c, d}가 되었으므로, d와 연결된 변 de(2), df(3), db(5) 중에서 가중치가 낮은 변 de(2)를 선택한다. S={a, c, d, e}가 되었으므로, e와 연결된 변 ef(2), eb(2) 중에서 ef(2)를 선택한다. S={a, c, d, e, f}에서 f와 변으로 연결된 점은 V={b} 중에 없으므로, 다시 e와 연결된 변 eb(2)를 선택한다. S={a, c, d, e, f, b}가 되고, 프림 알고리즘은 종료된다. 이 때 가중치는 1+1+2+2+2=8이다.
소개글