matlab图论程序算法大全.doc

1图论算法matlab实现求最小费用最大流算法的 MATLAB 程序代码如下：n=5;C=0 15 16 0 00 0 0 13 140 11 0 17 00 0 0 0 80 0 0 0 0; %弧容量b=0 4 1 0 00 0 0 6 10 2 0 3 00 0 0 0 20 0 0 0 0; %弧上单位流量的费用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;endfor(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;endif(pd)break;end;end %求最短路的Ford 算法结束if(p(n)=Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有向赋权图中不会含负权回路, 所以不会出现k=ndvt=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;endif(s(t)=1)break;end %当t 的标号为vs 时, 终止计算调整量t=s(t);end %继续调整前一段弧上的流fpd=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);endif(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-22wf %显示最小费用最大流量zwf %显示最小费用, 程序结束_Kruskal 避圈法：Kruskal 避圈法的MATLAB 程序代码如下：n=8;A=0 2 8 1 0 0 0 02 0 6 0 1 0 0 08 6 0 7 5 1 2 01 0 7 0 0 0 9 00 1 5 0 0 3 0 80 0 1 0 3 0 4 60 0 2 9 0 4 0 30 0 0 0 8 6 3 0;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;endk=k-1 %显示A中所有不同正数的个数for(i=1:k-1)for(j=i+1:k) %将x 中不同的正数从小到大排序if(x(j)<x(i)xx=x(j);x(j)=x(i);x(i)=xx;end;end;endT(n,n)=0; %将矩阵T 中所有的元素赋值为0q=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; %临时记录Twhile(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;endif(pd)T(i,j)=0;T(j,i)=0; %假如TT 中有圈else q=q+1;end;end;end;end;endT %显示近似最小生成树T, 程序结束用Warshall-Floyd 算法求任意两点间的最短路.n=8;A=0 2 8 1 Inf Inf Inf Inf2 0 6 Inf 1 Inf Inf Inf8 6 0 7 5 1 2 Inf1 Inf 7 0 Inf Inf 9 InfInf 1 5 Inf 0 3 Inf 8Inf Inf 1 Inf 3 0 4 6Inf Inf 2 9 Inf 4 0 3Inf Inf Inf Inf 8 6 3 0; % 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)<D(i,j)D(i,j)=D(i,k)+D(k,j); %更新dijR(i,j)=k;end;end;end %更新rijk %显示迭代步数D %显示每步迭代后的路长R %显示每步迭代后的路径pd=0;for i=1:n %含有负权时if(D(i,i)<0)pd=1;break;end;end %存在一条含有顶点vi 的负回路if(pd)break;end %存在一条负回路, 终止程序end %程序结束利用 Ford-Fulkerson 标号法求最大流算法的MATLAB 程序代码如下：n=8;C=0 5 4 3 0 0 0 00 0 0 0 5 3 0 00 0 0 0 0 3 2 00 0 0 0 0 0 2 00 0 0 0 0 0 0 40 0 0 0 0 0 0 30 0 0 0 0 0 0 50 0 0 0 0 0 0 0; %弧容量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-19while(1)No(1)=n+1;d(1)=Inf; %给发点vs 标号while(1)pd=1; %标号过程for(i=1:n)if(No(i) %选择一个已标号的点vifor(j=1:n)if(No(j)=0&f(i,j)<C(i,j) %对于未给标号的点vj, 当vivj 为非饱和弧时No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;if(d(j)>d(i)d(j)=d(i);endelseif(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;endif(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; %继续调整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);end %计算最大流量f %显示最大流wf %显示最大流量No %显示标号, 由此可得最小割, 程序结束图论程序大全程序一：关联矩阵和邻接矩阵互换算法function W=incandadf(F,f)if f=0 m=sum(sum(F)/2; n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)=0 W(i,k)=1; W(j,k)=1; k=k+1; end end endelseif f=1 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)=0); W(a(1),a(2)=1; W(a(2),a(1)=1; endelse fprint('Please imput the right value of f');endW;程序二：可达矩阵算法function P=dgraf(A)n=size(A,1);P=A;for i=2:n P=P+Ai;endP(P=0)=1; P;程序三：有向图关联矩阵和邻接矩阵互换算法function W=mattransf(F,f)if f=0 m=sum(sum(F); n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)=0 W(i,k)=1; W(j,k)=-1; k=k+1; end end endelseif f=1 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)=0); if F(a(1),i)=1 W(a(1),a(2)=1; else W(a(2),a(1)=1; end end else fprint('Please imput the right value of f');endW;第二讲：最短路问题程序一：Dijkstra算法（计算两点间的最短路）function l,z=Dijkstra(W)n = size (W,1);for i = 1 :n l(i)=W(1,i); z(i)=0;end i=1;while i<=n for j =1 :n if l(i)>l(j)+W(j,i) l(i)=l(j)+W(j,i); z(i)=j-1; if j<i i=j-1; end end end i=i+1;end程序二：floyd算法（计算任意两点间的最短距离）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 r; 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程序三：n2short.m 计算指定两点间的最短距离function P u=n2short(W,k1,k2)n=length(W);U=W;m=1;while m<=n for i=1:n for j=1:n if U(i,j)>U(i,m)+U(m,j) U(i,j)=U(i,m)+U(m,j); end end end m=m+1;endu=U(k1,k2);P1=zeros(1,n);k=1;P1(k)=k2;V=ones(1,n)*inf;kk=k2;while kk=k1 for i=1:n V(1,i)=U(k1,kk)-W(i,kk); if V(1,i)=U(k1,i) P1(k+1)=i; kk=i; k=k+1; end endendk=1;wrow=find(P1=0);for j=length(wrow):-1:1 P(k)=P1(wrow(j); k=k+1;endP;程序四、n1short.m(计算某点到其它所有点的最短距离)functionPm D=n1short(W,k)n=size(W,1);D=zeros(1,n);for i=1:n P d=n2short(W,k,i); Pmi=P; D(i)=d;end程序五：pass2short.m(计算经过某两点的最短距离)function P d=pass2short(W,k1,k2,t1,t2) p1 d1=n2short(W,k1,t1);p2 d2=n2short(W,t1,t2);p3 d3=n2short(W,t2,k2);dt1=d1+d2+d3;p4 d4=n2short(W,k1,t2);p5 d5=n2short(W,t2,t1);p6 d6=n2short(W,t1,k2);dt2=d4+d5+d6;if dt1<dt2 d=dt1; P=p1 p2(2:length(p2) p3(2:length(p3);else d=dt1; p=p4 p5(2:length(p5) p6(2:length(p6);endP;d;第三讲：最小生成树程序一：最小生成树的Kruskal算法function T c=krusf(d,flag)if nargin=1 n=size(d,2); m=sum(sum(d=0)/2; b=zeros(3,m); k=1; for i=1:n for j=(i+1):n if d(i,j)=0 b(1,k)=i;b(2,k)=j; b(3,k)=d(i,j); k=k+1; end end endelse 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; for i=1:m if t(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); for j=1:n if t(j)=tmax t(j)=tmin; end end end if k=n break; end endT; c;程序二：最小生成树的Prim算法function T c=Primf(a)l=length(a);a(a=0)=inf;k=1:l;listV(k)=0;listV(1)=1;e=1;while (e<l) min=inf; for i=1:l if listV(i)=1 for j=1:l if listV(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;endT=source;destination;for g=1:e-1 c(g)=a(T(1,g),T(2,g);endc;另外两种程序最小生成树程序1（prim 算法构造最小生成树）a=inf 50 60 inf inf inf inf;50 inf inf 65 40 inf inf;60 inf inf 52 inf inf 45;. inf 65 52 inf 50 30 42;inf 40 inf 50 inf 70 inf;inf inf inf 30 70 inf inf;. inf inf 45 42 inf inf inf;result=;p=1;tb=2:length(a);while length(result)=length(a)-1temp=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)=;endresult 最小生成树程序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=;while length(result)<looptemp=min(data(3,:);flag=find(data(3,:)=temp);flag=flag(1);v1=data(1,flag);v2=data(2,flag);if index(1,flag)=index(2,flag)result=result,data(:,flag);endindex(find(index=v2)=v1;data(:,flag)=;index(:,flag)=;endresult第四讲：Euler图和Hamilton图程序一：Fleury算法（在一个Euler图中找出Euler环游）注：包括三个文件；fleuf1.m, edf.m, flecvexf.mfunction T c=fleuf1(d)%注：必须保证是Euler环游，否则输出T=0,c=0n=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;for i=1:n if mod(a(i),2)=1 m=m+1; endendif m=0 fprintf('there is not exit Euler path.n') T=0;c=0;endif m=0 vet=1; flag=0; t1=find(matr(vet,:)=1); for ii=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; while flagg flagg ed=edf(matr,eds,vexs,ed,tem); tem=tem+1; if ed(1,eds)=0 & ed(2,eds)=0 T=ed; T(2,eds)=1; c=0; for g=1:eds c=c+d(T(1,g),T(2,g); end flagg=0; break; end end endendfunctionflag ed=edf(matr,eds,vexs,ed,tem)flag=1;for i=2:eds dvex f=flecvexf(matr,i,vexs,eds,ed,tem); if f=1 flag=0; break; end if dvex=0 ed(:,i)=vexs(1,i) dvex; vexs(1,i+1)=dvex; matr(vexs(1,i+1),vexs(1,i)=0; else break; endendfunction dvex f=flecvexf(matr,i,vexs,eds,ed,temp)f=0;edd=find(matr(vexs(1,i),:)=1);dvex=0;dvex1=;ded=;if length(edd)=1 dvex=edd;else dd=1;dd1=0;kkk=0; for kk=1:length(edd) m1=find(vexs=edd(kk); if sum(m1)=0 dvex1(dd)=edd(kk); dd=dd+1; dd1=1; else kkk=kkk+1; end end if kkk=length(edd) tem=vexs(1,i)*ones(1,kkk); edd1=tem;edd; for l1=1:kkk lt=0;ddd=1; for l2=1:eds if edd1(1:2,l1)=ed(1:2,l2) lt=lt+1; end end if lt=0 ded(ddd)=edd(l1); ddd=ddd+1; end end end if temp<=length(dvex1) dvex=dvex1(temp); elseif temp>length(dvex1) & temp<=length(ded) dvex=ded(temp); else f=1; endend程序二：Hamilton改良圈算法（找出比较好的Hamilton路）function C d1= hamiltonglf(v)%d表示权值矩阵%C表示算法最终找到的Hamilton圈。%v = 51 67;37 84;41 94;2 99;18 54;4 50;24 42;25 38;13 40;7 64;22 60;25 62;18 40;41 26;n=size(v,1);subplot(1,2,1)hold on;plot (v(:,1),v(:,2),'*'); %描点for i=1:n str1='V'str2=num2str(i); dot=str1,str2; text(v(i,1)-1,v(i,2)-2,dot); %给点命名endplot (v(:,1),v(:,2);%连线plot(v(n,1),v(1,1),v(n,2),v(1,2);for i =1:n for j=1:n d(i,j)=sqrt(v(i,1)-v(j,1)2+(v(i,2)-v(j,2)2); endendd2=0;for i=1:n if i<n d2=d2+d(i,i+1); else d2=d2+d(n,1); endendtext(10,30,num2str(d2);n=size(d,2);C=linspace(1,n,n) 1;for nnn=1:20 C1=C; if n>3 for m=4:n+1 for i=1:(m-3) for j=(i+2):(m-1) if (d(C(i),C(j)+d(C(i+1),C(j+1)<d(C(i),C(i+1)+d(C(j),C(j+1) C1(1:i)=C(1:i); for k=(i+1):j C1(k)=C(j+i+1-k); end C1(j+1):m)=C(j+1):m); end end end end elseif n<=3 if n<=2 fprint('It does not exist Hamilton circle.'); else fprint('Any cirlce is the right answer.'); end end C=C1; d1=0; for i=1:n d1=d1+d(C(i),C(i+1); endd1;endsubplot(1,2,2);hold on;plot (v(:,1),v(:,2),'*'); %描点for i=1:n str1='V'str2=num2str(i); dot=str1,str2; text(v(i,1)-1,v(i,2)-2,dot); %给点命名endv2=v;v(1,1),v(1,2);plot(v(C(:),1),v(C(:),2),'r');text(10,30,num2str(d1);第五讲：匹配问题及算法程序一：较大基础匹配算法function J=matgraf(W)n=size(W,1);J=zeros(n,n);while sum(sum(W)=0 a=find(W=0); t1=mod(a(1),n); if t1=0 t1=n; end if a(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;endJ;程序二：匈牙利算法（完美匹配算法,包括三个文件fc01,fc02,fc03）function e,s=fc01(a,flag)if nargin=1 flag=0;endb=a;if flag=0 cmax=max(max(b)'); b=cmax-b;endm=size(b);for i =1:m(1) b(i,:)=b(i,:)-min(b(i,:);endfor j=1:m(2) b(:,j)=b(:,j)-min(b(:,j);endd=(b=0);e,total=fc02(d);while total=m(1) b=fc03(b,e); d=(b=0); e,total=fc02(d);endinx=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')