0123456789101112
prim_알고리즘.ppt
Prim 알고리즘의 정의
최소비용 신장트리(MST)
-주어진 그래프의 신장트리 중 전체 가중치의 합이 최소가 되는 것
우선순위 우선탐색(PFS)방식
-가설비용에 해당하는 간선에 가중치를 두고 가중치가 작은 것일수록 우선순위가 높다고 정의한 것
1. 시작할 정점을 임의로 선택한다.
2. 선택된 정점들에 부속된 간선들 중 가중치가 제일 작은 간선을 선택하여 최소 비용 신장 트리에 포함시킨다.
3. 선택된 간선에 인접한 정점들에 부속된 간선들에 대해서도 2를 반복한다.
4. 만약 사이클이 발생하면 선택한 간선은 제거하고 그 다음 가중치가 작은 간선이 있으면 선택하고 없으면 그 전에 방문한 정점에 연결된 간선에 대해 2를 반복한다.
5. 모든 정점이 연결되면 종료한다.
% Program 'prim_1.m' (ver. 1.1) 이음선의 잘못된 출력 수정
% 강의명 : 알고리즘, 담당교수 : 송오영 교수님, 조이름 : 8조
% prim algorithm
% 문의 : noota@daum.net
% 인접행렬 생성 부분!!
% 자동생성
% ---------------------------------------------------------------------
n=input('노드의 개수를 입력하세요.'); % n에 노드 개수를 입력받음.
A = randint(n,n,[1,100]); % 1~100까지의 임의의 수를 갖는 n행 n열 행렬A 생성.
% 노드의 개수가 증가하면 임의의 수 영역을 넓혀주는 것이 결과값 보기에 좋음.
% 그렇지 않을 경우 확률적으로 같은 비용을 가지는 경로가 많아지므로.
% 후반부에는 노드가 순차적으로 나열되는 경향이 나타남.
for a1=1:n
for a2=a1+1:n % 상위 삼각형만 확인하게 조정.
if A(a1,a2)>=50 % 절반정도의 끊어진 이음선 생성
A(a1,a2)=inf;
end % 10 값을 가지면 inf으로 변환, 경로가 없는것으로 취급.
A(a2,a1)=A(a1,a2); % 방향성이 없으므로 같은노드연결값 동일하게함.
end % 행렬의 각 열을 확인하기위한 반복문.
A(a1,a1)=0; % 자신의 노드에서 자신의 노드로 오는경우는 0으로 처리.
end % 행렬의 각 행을 확인하기위한 반복문.
A % 생성된 행렬 출력
% 수동생성
% ---------------------------------------------------------------------
%A=[0 1 3 inf inf
% 1 0 3 6 inf
% 3 3 0 4 2
% inf 6 4 0 5
% inf inf 2 5 0]
%n=length(A);
% ---------------------------------------------------------------------
disp('인접행렬 생성!')
% 결과값을 출력할 행렬 3개 생성
% ---------------------------------------------------------------------
% 유망한 집합, 연결되는 노드 모두 처음은 노드1값을 가지므로 1로된 행렬 생성.
disp('유망한 집합 P1생성!')
P1=ones(1,n) % 1로 이루어진 1행 n열 행렬 생성
% 어느노드에서 연결하는지 지속적으로 나타낼 P2생성!
P2=ones(1,n); % 1로 이루어진 1행 n열 행렬 생성
% 유망한 노드에 최소비용으로 연결하는 노드 나타낼 P3생성!
% P3=ones(1,n); % 1로 이루어진 1행 n열 행렬 생성 (필요없게됨!!!)
% 어느노드에서 연결하는지는 최종적으로 나타낼 P4생성!
P4=ones(1,n-1); % 1로 이루어진 1행 n-1열 행렬 생성
%n10=input('[쉬어가기] 엔터를 치면 계속 진행 됩니다.');
% ---------------------------------------------------------------------
% 최소비용 신장트리를 생성하는 부분
% ---------------------------------------------------------------------
for c=1:n-1
% 비용이 적게드는 노드를 찾는 부분
% ---------------------------------------------------------------------
min1=inf; % 작은비용을 찾기 위해 사용할 변수'min1'을 inf로 초기화.
for b1=1:n
if (A(1,b1)~=0)&&(min1>A(1,b1))
min1=A(1,b1); %위의 두 조건 만족하면 min1값 대체
inx=b1; % 최소값의 노드 'inx' 변수에 기억.
end % 0은 이미 포함된 노드이므로 제외하고, min1보다 작은 것 찾음.
end % n번 반복 실행해서 최소비용으로 갈 수있는 노드 찾음.
% ---------------------------------------------------------------------
disp('유망한 집합 P1!')
P1(1,c+1)=inx % 유망한 집합에 찾아낸 유망한 노드 입력후 출력.
disp('연결노드 P4!')
P4(1,c)=P2(1,inx) % 유망한 노드를 어디서 연결하는지 나타내는 부분.
% 유망한 노드의 비용을 유망한 집합의 비용과 합치는 부분
% ---------------------------------------------------------------------
for b2=1:n
if (A(1,b2)==inf)&&(A(inx,b2)==inf)
A(1,b2)=inf;
else
if A(1,b2)>A(inx,b2)
A(1,b2)=A(inx,b2);
%inx
if b2~=inx
P2(1,b2)=inx; % 적은 비용을 가지는 노드 그때 그때 새로 업데이트
end
end % 유망한 노드를 가져올때 비교해서 적은 비용을 취함.
end % 둘다 inf면 inf값을 유지함. 어차피 끊어진 것이므로.
end % 행렬 두개를 하나로 묶기 위한 반복문.
% ---------------------------------------------------------------------
% -빼버린부분 시작-
% P3 부분은 빼고 P2에서 P4로 전달되게 수정하였습니다.
% P3(1,c:n-1)=P2(1,c:n-1); % 이미 연결된 부분은 수정이 불가능하므로 제외
% -빼버린부분 끝-
disp('합친행렬표시')
A
%n10=input('[쉬어가기] 엔터를 치면 계속 진행 됩니다.');
end
% 연결을 하던중 이음선이 모두 inf인 노드가 남아있으면
% 유망한 노드집합의 마지막 노드가 반복됩니다.
% 노드의 갯수가 작아지면 끊어진 이음선의 확률을 줄여주는 것이 좋습니다.
% 노드의 갯수가 적어지면 모든 끊길 확률이 노드가 많으 때 비해 증가하기 때문.
% 21행의 마지막부분의 수치를 높이면 끊어진 이음선이 생길 확률이 줄어듭니다.
% 위의 수치는 14행의 변수 범위 안에서 정해야 올바른 결과를 얻을 수 있습니다.
코드설명.doc