图论算法及其Matla程序b程序.docVIP

求单源最短路径的Dijkstra算法的Matlab程序 function [d index1 index2]=Dijkf(a) M=max(max(a)); pb(1:length(a))=0; pb(1)=1; index1=1; index2=ones(1,length(a)); d(1:length(a))=M;d(1)=0;temp=1; while sum(pb)length(a) tb=find(pb==0); d(tb)=min(d(tb),d(temp)+a(temp,tb)); tmpb=find(d(tb)==min(d(tb))); temp=tb(tmpb(1)); pb(temp)=1; index1=[index1,temp]; index=index1(find(d(index1)==d(temp)-a(temp,index1))); if length(index)=2 index=index(1); end index2(temp)=index; end d; index1; index2; 求任意两点间最短路的Floyd算法的Matlab程序 function [D,R]=floyd(a) n=size(a,1); D=a; for i=1:n for j=1:n R(i,j)=j; end end for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=R(i,k); end end end end D;R ; 求Euler回路的Fleury算法的Matlab程序 function [eu,cEu]=arEuler(E) eu=0; cEu=[]; ncV=arComp(E); if max(ncV)1 return end n=max(max(E(:,1:2))); m=size(E,1); for i=1:n b(i)=0; for j=1:m if E(j,1)==i|E(j,2)==i b(i)=b(i)+1; end end end rp=rem(b,2); srp=sum(rp); switch srp case 0, eu=1; case 2, eu=0.5; otherwise, return end if srp==0 v1=1; else v1=find(rp); v1=v1(1); end vc=v1; m=size(E,1); E1=[E(:,1:2),[1:m]]; while ~isempty(E1) evc=find((E1(:,1)==vc)|(E1(:,2)==vc)); levc=length(evc); if levc==1 cEu=[cEu;E1(evc,3)]; vcold=vc; vc=sum(E1(evc,1:2))-vc; E1=E1(setdiff([1:size(E1,1)],evc),:); E2=E1(:,1:2); E2gv=E2vcold; E2(E2gv)=E2(E2gv)-1; E1(:,1:2)=E2; if vcvcold vc=vc-1; end if v1vcold v1=v1-1; end else for k=1:levc E2=E1(setdiff([1:size(E1,1)],evc(k)),:); ncv=arComp(E2); nco=max(ncv); if (max(ncv)==1) cEu=[cEu;E1(