图论算法及其Matlab程序

求单源最短路径的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)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,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=E2>vcold;

E2(E2gv)=E2(E2gv)-1;

E1(:,1:2)=E2;

if vc>vcold

vc=vc-1;

end

if v1>vcold

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

end

end

return

求最小生成树的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);

end

while size(T,2)[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 db(1,j)=v;b(3,j)=d;

end

end

end

T;e;

求最小生成树的Kruskal算法的Matlab程序

function [T c]=kruskal(a)

n=size(a,1);

m=0;

for i=1:n-1

for j=i+1:n

if a(i,j)>0&a(i,j)m=m+1;b(1,m)=i;b(2,m)=j;

b(3,m)=a(i,j);

end

end

end

[B,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;

end

end

t,c

求Huffman树的Matlab程序

function [h,l]=huffman(p)

if (length(find(p<0))~=0)

error('Not a prob,negative component');

end

if (abs(sum(p)-1)>10e-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);

h

l

最大流算法Matlab程序

function [f wf No]=fofuf(C,f1)

n=length(C);

if nargin==1;

f=zeros(n,n);

else

f=f1;

end

No=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)No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;

if (d(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(t)<0)

f(No(t),t)=f(No(t),t)-dvt;

end

if (No(t)==1)

for (i=1:n)

No(i)=0;d(i)=0;

end

break

end

t=No(t);

end

end

wf=0;

for (j=1:n)

wf=wf+f(1,j);

end

f;

wf;

No;