알고리즘 강좌 5회

목차

이글은 알고리즘에 대한 글입니다.

본문내용

array[1..n,1..n] of integer =(
(0,1,3,0,0),
(1,0,3,6,0),
(3,3,0,4,2),
(0,6,4,0,5),
(0,0,2,5,0)
);
var
tree,selected : array[1..n] of integer;
i,j,k : integer;
min,edge : integer;
sum : integer;
begin
tree[1]:=1; {정점A를 선택}
selected[1]:=1;
for i:=2 to n do begin
min:=maxint;
for j:=1 to i-1 do begin
for k:=1 to n do begin
if (D[tree[j],k]0)
and (selected[k]=0) then begin
{가장 가까운 선택되지 않은 정점을 찾는다}
min:=D[tree[j],k];
edge:=k;
end;
end;
end;
inc(sum,min);
tree[i]:=edge; {정점 추가}
selected[tree[i]]:=1;
end;
writeln(sum);
end.
실제로 Prim의 알고리즘은 시간복잡도가 n2이지만 여기서는 이해를 편하게 할 목적으로 조금 풀어서 코딩했기때문에 n3이 되고 말았다(-_-;;)
-------------------------------------------------------------------------------------
오늘은 여기까지 쓰겠습니다 헥헥-_-
질문은 Q/A란에 해주시면 답변 빨리 달아드립알고리즘 강좌 5회니다.
흐음. 조만간에 2회 올리도록 하죠.

키워드

알고리즘,   강좌,   그리디,   그리디의 실제,   Greedy