图论matlab程序.docx
《图论matlab程序.docx》由会员分享,可在线阅读,更多相关《图论matlab程序.docx(27页珍藏版)》请在冰点文库上搜索。
图论matlab程序
第一讲:
图论模型
程序一:
可达矩阵算法
functionP=dgraf(A)
n=size(A,1);
P=A;
fori=2:
n
P=P+A^i;
end
P(P~=0)=1;
P;
程序二:
关联矩阵和邻接矩阵互换算法
functionW=incandadf(F,f)
iff==0
m=sum(sum(F))/2;
n=size(F,1);
W=zeros(n,m);
k=1;
fori=1:
n
forj=i:
n
ifF(i,j)~=0
W(i,k)=1;
W(j,k)=1;
k=k+1;
end
end
end
elseiff==1
m=size(F,2);
n=size(F,1);
W=zeros(n,n);
fori=1:
m
a=find(F(:
i)~=0);
W(a
(1),a
(2))=1;
W(a
(2),a
(1))=1;
end
else
fprint('Pleaseimputtherightvalueoff');
end
W;
程序三:
有向图关联矩阵和邻接矩阵互换算法
functionW=mattransf(F,f)
iff==0
m=sum(sum(F));
n=size(F,1);
W=zeros(n,m);
k=1;
fori=1:
n
forj=i:
n
ifF(i,j)~=0
W(i,k)=1;
W(j,k)=-1;
k=k+1;
end
end
end
elseiff==1
m=size(F,2);
n=size(F,1);
W=zeros(n,n);
fori=1:
m
a=find(F(:
i)~=0);
ifF(a
(1),i)==1
W(a
(1),a
(2))=1;
else
W(a
(2),a
(1))=1;
end
end
else
fprint('Pleaseimputtherightvalueoff');
end
W;
第二讲:
最短路问题
程序一:
Dijkstra算法(计算两点间的最短路)
function[l,z]=Dijkstra(W)
n=size(W,1);
fori=1:
n
l(i)=W(1,i);
z(i)=0;
end
i=1;
whilei<=n
forj=1:
n
ifl(i)>l(j)+W(j,i)
l(i)=l(j)+W(j,i);
z(i)=j-1;
ifj
i=j-1;
end
end
end
i=i+1;
end
程序二:
floyd算法(计算任意两点间的最短距离)
function[d,r]=floyd(a)
n=size(a,1);
d=a;
fori=1:
n
forj=1:
n
r(i,j)=j;
end
end
r;
fork=1:
n
fori=1:
n
forj=1:
n
ifd(i,k)+d(k,j)d(i,j)=d(i,k)+d(k,j);
r(i,j)=r(i,k);
end
end
end
end
程序三:
n2short.m计算指定两点间的最短距离
function[Pu]=n2short(W,k1,k2)
n=length(W);
U=W;
m=1;
whilem<=n
fori=1:
n
forj=1:
n
ifU(i,j)>U(i,m)+U(m,j)
U(i,j)=U(i,m)+U(m,j);
end
end
end
m=m+1;
end
u=U(k1,k2);
P1=zeros(1,n);
k=1;
P1(k)=k2;
V=ones(1,n)*inf;
kk=k2;
whilekk~=k1
fori=1:
n
V(1,i)=U(k1,kk)-W(i,kk);
ifV(1,i)==U(k1,i)
P1(k+1)=i;
kk=i;
k=k+1;
end
end
end
k=1;
wrow=find(P1~=0);
forj=length(wrow):
-1:
1
P(k)=P1(wrow(j));
k=k+1;
end
P;
程序四、n1short.m(计算某点到其它所有点的最短距离)
function[PmD]=n1short(W,k)
n=size(W,1);
D=zeros(1,n);
fori=1:
n
[Pd]=n2short(W,k,i);
Pm{i}=P;
D(i)=d;
end
程序五:
pass2short.m(计算经过某两点的最短距离)
function[Pd]=pass2short(W,k1,k2,t1,t2)
[p1d1]=n2short(W,k1,t1);
[p2d2]=n2short(W,t1,t2);
[p3d3]=n2short(W,t2,k2);
dt1=d1+d2+d3;
[p4d4]=n2short(W,k1,t2);
[p5d5]=n2short(W,t2,t1);
[p6d6]=n2short(W,t1,k2);
dt2=d4+d5+d6;
ifdt1d=dt1;
P=[p1p2(2:
length(p2))p3(2:
length(p3))];
else
d=dt1;
p=[p4p5(2:
length(p5))p6(2:
length(p6))];
end
P;
d;
第三讲:
最小生成树
程序一:
最小生成树的Kruskal算法
function[Tc]=krusf(d,flag)
ifnargin==1
n=size(d,2);
m=sum(sum(d~=0))/2;
b=zeros(3,m);
k=1;
fori=1:
n
forj=(i+1):
n
ifd(i,j)~=0
b(1,k)=i;b(2,k)=j;
b(3,k)=d(i,j);
k=k+1;
end
end
end
else
b=d;
end
n=max(max(b(1:
2,:
)));
m=size(b,2);
[B,i]=sortrows(b',3);
B=B';
c=0;T=[];
k=1;t=1:
n;
fori=1:
m
ift(B(1,i))~=t(B(2,i))
T(1:
2,k)=B(1:
2,i);
c=c+B(3,i);
k=k+1;
tmin=min(t(B(1,i)),t(B(2,i)));
tmax=max(t(B(1,i)),t(B(2,i)));
forj=1:
n
ift(j)==tmax
t(j)=tmin;
end
end
end
ifk==n
break;
end
end
T;
c;
程序二:
最小生成树的Prim算法
function[Tc]=Primf(a)
l=length(a);
a(a==0)=inf;
k=1:
l;
listV(k)=0;
listV
(1)=1;
e=1;
while(emin=inf;
fori=1:
l
iflistV(i)==1
forj=1:
l
iflistV(j)==0&min>a(i,j)
min=a(i,j);b=a(i,j);
s=i;d=j;
end
end
end
end
listV(d)=1;
distance(e)=b;
source(e)=s;
destination(e)=d;
e=e+1;
end
T=[source;destination];
forg=1:
e-1
c(g)=a(T(1,g),T(2,g));
end
c;
第四讲:
Euler图和Hamilton图
程序一:
Fleury算法(在一个Euler图中找出Euler环游)
注:
包括三个文件;fleuf1.m,edf.m,flecvexf.m
function[Tc]=fleuf1(d)
%注:
必须保证是Euler环游,否则输出T=0,c=0
n=length(d);
b=d;
b(b==inf)=0;
b(b~=0)=1;
m=0;
a=sum(b);
eds=sum(a)/2;
ed=zeros(2,eds);
vexs=zeros(1,eds+1);
matr=b;
fori=1:
n
ifmod(a(i),2)==1
m=m+1;
end
end
ifm~=0
fprintf('thereisnotexitEulerpath.\n')
T=0;c=0;
end
ifm==0
vet=1;
flag=0;
t1=find(matr(vet,:
)==1);
forii=1:
length(t1)
ed(:
1)=[vet,t1(ii)];
vexs(1,1)=vet;vexs(1,2)=t1(ii);
matr(vexs(1,2),vexs(1,1))=0;
flagg=1;tem=1;
whileflagg
[flagged]=edf(matr,eds,vexs,ed,tem);
tem=tem+1;
ifed(1,eds)~=0&ed(2,eds)~=0
T=ed;
T(2,eds)=1;
c=0;
forg=1:
eds
c=c+d(T(1,g),T(2,g));
end
flagg=0;
break;
end
end
end
end
function[flaged]=edf(matr,eds,vexs,ed,tem)
flag=1;
fori=2:
eds
[dvexf]=flecvexf(matr,i,vexs,eds,ed,tem);
iff==1
flag=0;
break;
end
ifdvex~=0
ed(:
i)=[vexs(1,i)dvex];
vexs(1,i+1)=dvex;
matr(vexs(1,i+1),vexs(1,i))=0;
else
break;
end
end
function[dvexf]=flecvexf(matr,i,vexs,eds,ed,temp)
f=0;
edd=find(matr(vexs(1,i),:
)==1);
dvex=0;
dvex1=[];
ded=[];
iflength(edd)==1
dvex=edd;
else
dd=1;dd1=0;kkk=0;
forkk=1:
length(edd)
m1=find(vexs==edd(kk));
ifsum(m1)==0
dvex1(dd)=edd(kk);
dd=dd+1;
dd1=1;
else
kkk=kkk+1;
end
end
ifkkk==length(edd)
tem=vexs(1,i)*ones(1,kkk);
edd1=[tem;edd];
forl1=1:
kkk
lt=0;ddd=1;
forl2=1:
eds
ifedd1(1:
2,l1)==ed(1:
2,l2)
lt=lt+1;
end
end
iflt==0
ded(ddd)=edd(l1);
ddd=ddd+1;
end
end
end
iftemp<=length(dvex1)
dvex=dvex1(temp);
elseiftemp>length(dvex1)&temp<=length(ded)
dvex=ded(temp);
else
f=1;
end
end
程序二:
Hamilton改良圈算法(找出比较好的Hamilton路)
function[Cd1]=hamiltonglf(v)
%d表示权值矩阵
%C表示算法最终找到的Hamilton圈。
%v=[5167;3784;4194;299;1854;450;2442;2538;1340;764;2260;2562;1840;4126];
n=size(v,1);
subplot(1,2,1)
holdon;
plot(v(:
1),v(:
2),'*');%描点
fori=1:
n
str1='V';str2=num2str(i);
dot=[str1,str2];
text(v(i,1)-1,v(i,2)-2,dot);%给点命名
end
plot(v(:
1),v(:
2));%连线
plot([v(n,1),v(1,1)],[v(n,2),v(1,2)]);
fori=1:
n
forj=1:
n
d(i,j)=sqrt((v(i,1)-v(j,1))^2+(v(i,2)-v(j,2))^2);
end
end
d2=0;
fori=1:
n
ifid2=d2+d(i,i+1);
else
d2=d2+d(n,1);
end
end
text(10,30,num2str(d2));
n=size(d,2);
C=[linspace(1,n,n)1];
fornnn=1:
20
C1=C;
ifn>3
form=4:
n+1
fori=1:
(m-3)
forj=(i+2):
(m-1)
if(d(C(i),C(j))+d(C(i+1),C(j+1))C1(1:
i)=C(1:
i);
fork=(i+1):
j
C1(k)=C(j+i+1-k);
end
C1((j+1):
m)=C((j+1):
m);
end
end
end
end
elseifn<=3
ifn<=2
fprint('ItdoesnotexistHamiltoncircle.');
else
fprint('Anycirlceistherightanswer.');
end
end
C=C1;
d1=0;
fori=1:
n
d1=d1+d(C(i),C(i+1));
end
d1;
end
subplot(1,2,2);
holdon;
plot(v(:
1),v(:
2),'*');%描点
fori=1:
n
str1='V';str2=num2str(i);
dot=[str1,str2];
text(v(i,1)-1,v(i,2)-2,dot);%给点命名
end
v2=[v;v(1,1),v(1,2)];
plot(v(C(:
),1),v(C(:
),2),'r');
text(10,30,num2str(d1));
第五讲:
匹配问题及算法
程序一:
较大基础匹配算法
functionJ=matgraf(W)
n=size(W,1);
J=zeros(n,n);
whilesum(sum(W))~=0
a=find(W~=0);
t1=mod(a
(1),n);
ift1==0
t1=n;
end
ifa
(1)/n>floor(a
(1)/n)
t2=floor(a
(1)/n)+1;
else
t2=floor(a
(1)/n);
end
J(t1,t2)=1,J(t2,t1)=1;
W(t1,:
)=0;W(t2,:
)=0;
W(:
t1)=0;W(:
t2)=0;
end
J;
程序二:
匈牙利算法(完美匹配算法,包括三个文件fc01,fc02,fc03)
function[e,s]=fc01(a,flag)
ifnargin==1
flag=0;
end
b=a;
ifflag==0
cmax=max(max(b)');
b=cmax-b;
end
m=size(b);
fori=1:
m
(1)
b(i,:
)=b(i,:
)-min(b(i,:
));
end
forj=1:
m
(2)
b(:
j)=b(:
j)-min(b(:
j));
end
d=(b==0);
[e,total]=fc02(d);
whiletotal~=m
(1)
b=fc03(b,e);
d=(b==0);
[e,total]=fc02(d);
end
inx=sub2ind(size(a),e(:
1),e(:
2));
e=[e,a(inx)];
s=sum(a(inx));
function[e,total]=fc02(d)
total=0;m=size(d);
e=zeros(m
(1),2);
t=sum(sum(d)');
nump=sum(d');
whilet~=0
[s,inp]=sort(nump);
inq=find(s);
ep=inp(inq
(1));
inp=find(d(ep,:
));
numq=sum(d(:
inp));
[s,inq]=sort(numq);
eq=inp(inq
(1));
total=total+1;
e(total,:
)=[ep,eq];
inp=find(d(:
eq));
nump(inp)=nump(inp)-1;
nump(ep)=0;
t=t-sum(d(ep,:
))-sum(d(:
eq))+1;
d(ep,:
)=0*d(ep,:
);
d(:
eq)=0*d(:
eq);
end
functionb=fc03(b,e)
m=size(b);t=1;
p=ones(m
(1),1);
q=zeros(m
(1),1);
inp=find(e(:
1)~=0);
p(e(inp,1))=0;
whilet~=0
tp=sum(p+q);
inp=find(p==1);
n=size(inp);
fori=1:
n
(1)
inq=find(b(inp(i),:
)==0);
q(inq)=1;
end
inp=find(q==1);
n=size(inp);
fori=1:
n
(1)
ifall(e(:
2)-inp(i))==0
inq=find((e(:
2)-inp(i))==0);
p(e(inq))=1;
end
end
tq=sum(p+q);
t=tq-tp;
end
inp=find(p==1);
inq=find(q==0);
cmin=min(min(b(inp,inq))');
inq=find(q==1);
b(inp,:
)=b(inp,:
)-cmin;
b(:
inq)=b(:
inq)+cmin;
第六讲:
最大流最小费用问题
程序一:
2F算法(Ford-Fulkerson算法),求最大流
%C=[05430000;00005300;00000320;00000020;
%00000004;00000003;00000005;00000000]
function[fwf]=fulkersonf(C,f1)
%C表示容量
%f1表示当前流量,默认为0
%f表示最大流±íʾ×î´óÁ÷
%wf表示最大流的流量
n=length(C);
ifnargin==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;
程序二:
Busacker-Gowan算法(求最大流最小费用)
%C=[0151600;0001314;0110170;00008;00000]
%b=[04100;00061;02030;00002;00000]
%function[fwfzwf]=BGf(C,b)
%C表示弧容量矩阵
%b表示弧上单位流量的费用
%f表示最大流最小费用矩阵
%wf最大流量
%zwf表示最小费用
n=size(C,2);
wf=0;wf0=inf;
f=zeros(n,n);
while
(1)
a=ones(n,n)*inf;
for(i=1:
n)
a(i,i)=0;
end
for(i=1:
n)
for(j=1:
n)
if(C(i,j)>0&f(i,j)==0)
a(i,j)=b(i,j);
elseif(C(i,j)>0&f(i,j)==C(i,j))
a(j,i)=-b(i,j);
elseif(C(i,j)>0)
a(i,j)=b(i,j);
a(j,i)=-b(i,j);
end
end
end
for(i=2:
n)
p(i)=inf;s(i)=i;
e