matlab图论程序算法大全.docx
《matlab图论程序算法大全.docx》由会员分享，可在线阅读，更多相关《matlab图论程序算法大全.docx（39页珍藏版）》请在冰点文库上搜索。
matlab图论程序算法大全
图论算法matlab实现
求最小费用最大流算法的MATLAB程序代码如下：
n=5;C=[0151600
0001314
0110170
00008
00000];%弧容量
b=[04100
00061
02030
00002
00000];%弧上单位流量的费用
wf=0;wf0=Inf;%wf表示最大流量,wf0表示预定的流量值
for（i=1:
n）for（j=1:
n）f（i,j）=0;end;end%取初始可行流f为零流
while
（1）
for（i=1:
n）for（j=1:
n）if（j~=i）a（i,j）=Inf;end;end;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;end%用Ford算法求最短路,赋初值
for（k=1:
n）pd=1;%求有向赋权图中vs到vt的最短路
for（i=2:
n）for（j=1:
n）if（p（i）>p（j）+a（j,i））p（i）=p（j）+a（j,i）;s（i）=j;pd=0;end;end;end
if（pd）break;end;end%求最短路的Ford算法结束
if（p（n）==Inf）break;end%不存在vs到vt的最短路,算法终止.注意在求最小费用最大流时构造有
向赋权图中不会含负权回路,所以不会出现k=n
dvt=Inf;t=n;%进入调整过程,dvt表示调整量
while
（1）%计算调整量
if（a（s（t）,t）>0）dvtt=C（s（t）,t）-f（s（t）,t）;%前向弧调整量
elseif（a（s（t）,t）<0）dvtt=f（t,s（t））;end%后向弧调整量
if（dvt>dvtt）dvt=dvtt;end
if（s（t）==1）break;end%当t的标号为vs时,终止计算调整量
t=s（t）;end%继续调整前一段弧上的流f
pd=0;if（wf+dvt>=wf0）dvt=wf0-wf;pd=1;end%如果最大流量大于或等于预定的流量值
t=n;while
（1）%调整过程
if（a（s（t）,t）>0）f（s（t）,t）=f（s（t）,t）+dvt;%前向弧调整
elseif（a（s（t）,t）<0）f（t,s（t））=f（t,s（t））-dvt;end%后向弧调整
if（s（t）==1）break;end%当t的标号为vs时,终止调整过程
t=s（t）;end
if（pd）break;end%如果最大流量达到预定的流量值
wf=0;for（j=1:
n）wf=wf+f（1,j）;end;end%计算最大流量
zwf=0;for（i=1:
n）for（j=1:
n）zwf=zwf+b（i,j）*f（i,j）;end;end%计算最小费用
f%显示最小费用最大流
图6-22
wf%显示最小费用最大流量
zwf%显示最小费用,程序结束__
Kruskal避圈法：
Kruskal避圈法的MATLAB程序代码如下：
n=8;A=[02810000
20601000
86075120
10700090
01500308
00103046
00290403
00008630];
k=1;%记录A中不同正数的个数
for（i=1:
n-1）for（j=i+1:
n）%此循环是查找A中所有不同的正数
if（A（i,j）>0）x（k）=A（i,j）;%数组x记录A中不同的正数
kk=1;%临时变量
for（s=1:
k-1）if（x（k）==x（s））kk=0;break;end;end%排除相同的正数
k=k+kk;end;end;end
k=k-1%显示A中所有不同正数的个数
for（i=1:
k-1）for（j=i+1:
k）%将x中不同的正数从小到大排序
if（x（j）T（n,n）=0;%将矩阵T中所有的元素赋值为0
q=0;%记录加入到树T中的边数
for（s=1:
k）if（q==n）break;end%获得最小生成树T,算法终止
for（i=1:
n-1）for（j=i+1:
n）if（A（i,j）==x（s））T（i,j）=x（s）;T（j,i）=x（s）;%加入边到树T中
TT=T;%临时记录T
while
（1）pd=1;%砍掉TT中所有的树枝
for（y=1:
n）kk=0;
for（z=1:
n）if（TT（y,z）>0）kk=kk+1;zz=z;end;end%寻找TT中的树枝
if（kk==1）TT（y,zz）=0;TT（zz,y）=0;pd=0;end;end%砍掉TT中的树枝
if（pd）break;end;end%已砍掉了TT中所有的树枝
pd=0;%判断TT中是否有圈
for（y=1:
n-1）for（z=y+1:
n）if（TT（y,z）>0）pd=1;break;end;end;end
if（pd）T（i,j）=0;T（j,i）=0;%假如TT中有圈
elseq=q+1;end;end;end;end;end
T%显示近似最小生成树T,程序结束
用Warshall-Floyd算法求任意两点间的最短路.
n=8;A=[0281InfInfInfInf
206Inf1InfInfInf
8607512Inf
1Inf70InfInf9Inf
Inf15Inf03Inf8
InfInf1Inf3046
InfInf29Inf403
InfInfInfInf8630];%MATLAB中,Inf表示∞
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）R（i,j）=k;end;end;end%更新rij
k%显示迭代步数
D%显示每步迭代后的路长
R%显示每步迭代后的路径
pd=0;fori=1:
n%含有负权时
if（D（i,i）<0）pd=1;break;end;end%存在一条含有顶点vi的负回路
if（pd）break;end%存在一条负回路,终止程序
end%程序结束
利用Ford--Fulkerson标号法求最大流算法的MATLAB程序代码如下：
n=8;C=[05430000
00005300
00000320
00000020
00000004
00000003
00000005
00000000];%弧容量
for（i=1:
n）for（j=1:
n）f（i,j）=0;end;end%取初始可行流f为零流
for（i=1:
n）No（i）=0;d（i）=0;end%No,d记录标号
图6-19
while
（1）
No
（1）=n+1;d
（1）=Inf;%给发点vs标号
while
（1）pd=1;%标号过程
for（i=1:
n）if（No（i））%选择一个已标号的点vi
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）%对于未给标号的点vj,当vjvi为非零流弧时
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%若收点vt得到标号或者无法标号,终止标号过程
if（pd）break;end%vt未得到标号,f已是最大流,算法终止
dvt=d（n）;t=n;%进入调整过程,dvt表示调整量
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的标号为vs时,终止调整过程
t=No（t）;end;end;%继续调整前一段弧上的流f
wf=0;for（j=1:
n）wf=wf+f（1,j）;end%计算最大流量
f%显示最大流
wf%显示最大流量
No%显示标号,由此可得最小割,程序结束
图论程序大全
程序一：
关联矩阵和邻接矩阵互换算法
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;
程序二：
可达矩阵算法
functionP=dgraf（A）
n=size（A,1）;
P=A;
fori=2:
n
P=P+A^i;
end
P（P~=0）=1;
P;
程序三：
有向图关联矩阵和邻接矩阵互换算法
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;
ifji=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;
另外两种程序
最小生成树程序1（prim算法构造最小生成树）
a=[inf5060infinfinfinf;50infinf6540infinf;60infinf52infinf45;...
inf6552inf503042;inf40inf50inf70inf;infinfinf3070infinf;...
infinf4542infinfinf];
result=[];p=1;tb=2:
length（a）;
whilelength（result）~=length（a）-1
temp=a（p,tb）;temp=temp（:
）;
d=min（temp）;
[jb,kb]=find（a（p,tb）==d）;
j=p（jb
（1））;k=tb（kb
（1））;
result=[result,[j;k;d]];p=[p,k];tb（find（tb==k））=[];
end
result
最小生成树程序2（Kruskal算法构造最小生成树）
clc;clear;
a（1,2）=50;a（1,3）=60;a（2,4）=65;a（2,5）=40;
a（3,4）=52;a（3,7）=45;a（4,5）=50;a（4,6）=30;
a（4,7）=42;a（5,6）=70;
[i,j,b]=find（a）;
data=[i';j';b'];index=data（1:
2,:
）;
loop=max（size（a））-1;
result=[];
whilelength（result）temp=min（data（3,:
））;
flag=find（data（3,:
）==temp）;
flag=flag
（1）;
v1=data（1,flag）;v2=data（2,flag）;
ifindex（1,flag）~=index（2,flag）
result=[result,data（:
flag）];
end
index（find（index==v2））=v1;
data（:
flag）=[];
index（:
flag）=[];
end
result
第四讲：
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）
m
升级会员 