图论算法及其Matlab程序.doc

求单源最短路径的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)=2 index=index(1); end index2(temp)=index;endd;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; endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)1 return endn=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 endend rp=rem(b,2); srp=sum(rp); switch srp case 0, eu=1; case 2, eu=0.5; otherwise, returnend if srp=0 v1=1; else v1=find(rp); v1=v1(1); endvc=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(evc(k),3); vc=sum(E1(evc(k),1:2)-vc; E1=E2; break; end end endendreturn求最小生成树的Prim算法的Matlab程序function T e=prim(a)T=;e=0;v=1;n=size(a,1);c=2:n;for j=2:n b(1,j-1)=1; b(2,j-1)=j; b(3,j-1)=a(1,j);endwhile size(T,2)n-1 m,i=min(b(3,:); T(:,size(T,2)+1)=b(:,i); e=e+b(3,i); v=b(2,i); t=find(c=b(2,i);c(t)=; b(:,i)=; for j=1:length(c) d=a(v,b(2,j); if d0&a(i,j)inf m=m+1;b(1,m)=i;b(2,m)=j; b(3,m)=a(i,j); end endendB,i=sortrows(b,3);B=B;k=0;t=1:n;T=;c=0;for i=1:m if t(B(1,i)=t(B(2,i) k=k+1; T(:,k)=B(:,i); c=c+B(3,i); tmin=min(t(B(1,i),t(B(2,i); tmax=max(t(B(1,i),t(B(2,i); for j=1:n if t(j)=tmax t(j)=tmin; end end end if k=n-1 break; endendt,c求Huffman树的Matlab程序function h,l=huffman(p) if (length(find(p10e-10) error(Not a prob.vector,component do not add to 1) end n=length(p); q=p; m=zeros(n-1,n); for i=1:n-1 q,l=sort(q); m(i,:)=l(1:n-i+1),zeros(1,i-1); q=q(1)+q(2),q(3:n),1; end for i=1:n-1 c(i,:)=blanks(n*n); end c(n-1,n)=0; c(n-1,2*n)=1; for i=2:n-1 c(n-i,1:n-1)=c(n-i+1,n*(find(m(n-i+1,:)=1). -(n-2):n*(find(m(n-i+1,:)=1); c(n-i,n)=0; c(n-i,n+1:2*n-1)=c(n-i,1:n-1); c(n-i,2*n)=1; for j=1:i-1 c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,. n*(find(m(n-i+1,:)=j+1)-1)+1:n*find(m(n-i+1,:)=j+1); end end for i=1:n h(i,1:n)=c(1,n*(find(m(1,:)=i)-1)+1:find(m(1,:)=i)*n); ll(i)=length(find(abs(h(i,:)=32); end l=sum(p.*ll); hl 最大流算法Matlab程序function f wf No=fofuf(C,f1)n=length(C);if nargin=1; f=zeros(n,n);else f=f1;endNo=zeros(1,n);d=zeros(1,n);while (1) No(1)=n+1; d(1)=Inf; while (1) pd=1; for (i=1:n) if (No(i) for (j=1:n) if (No(j)=0&f(i,j)d(i) d(j)=d(i); end elseif (No(j)=0&f(j,i)0) No(j)=-i;d(j)=f(j,i);pd=0; if (d(j)d(i) d(j)=d(i); end end end end end if (No(n)|pd) break; end end if (pd) break; end dvt=d(n);t=n; while (1) if(No(t)0) f(No(t),t)=f(No(t),t)+dvt; elseif (No