(完整版)matlab图论程序算法大全,推荐文档

1、图论算法matlab实现精心整理求最小费用最大流算法的 matlab 程序代码如下：n=5;c=0 15 16 0 000 0 13 14011 0 17 000 0 0 800 0 0 0; %弧容量b=0 4 1 0 000061020300000200000; %弧上单位流量的费用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(

2、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 的最短路2019 年 9 月精心整理for(i=2:n)for(j=1:n)if(p(i)p(j)+a(j,i)p(i)=p(j)+a(j,i)

3、;s(i)=j;pd=0;end;end;endif(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)dvtt)dvt=dvtt;endif(s(t)=1)break;end %当t 的标号为vs

4、时, 终止计算调整量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)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中所有不同正数的个数fo

5、r(i=1:k-1)for(j=i+1:k) %将x 中不同的正数从小到大排序if(x(j)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 中有圈else q=q+1;end;end;end;e

6、nd;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%赋路

7、径初值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 %更新rij k %显示迭代步数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=

8、0 5 4 3 0 0 0 00000530000000320000000200000000400000003000000050 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)d(i)d(j)=

9、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; %前向弧调整else

10、if(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 %显示标号, 由此可得最小割, 程序结束图论程序大全程序一：关联矩阵和邻接矩阵互换算法function w=incandadf(f,f)if f=0m=sum(sum(f)/2;n=

11、size(f,1);w=zeros(n,m); k=1;for i=1:nfor j=i:nif f(i,j)=0w(i,k)=1;w(j,k)=1;k=k+1;endendendelseif f=1m=size(f,2);n=size(f,1);w=zeros(n,n); for i=1:ma=find(f(:,i)=0);w(a(1),a(2)=1;w(a(2),a(1)=1;end elsefprint(please imput the right value of f);end w;程序二：可达矩阵算法function p=dgraf(a)n=size(a,1);p=a;for i=2

12、:np=p+ai;end p(p=0)=1; p;程序三：有向图关联矩阵和邻接矩阵互换算法function w=mattransf(f,f)if f=0m=sum(sum(f);n=size(f,1);w=zeros(n,m); k=1;for i=1:nfor j=i:nif f(i,j)=0w(i,k)=1;w(j,k)=-1;k=k+1;endendendelseif f=1m=size(f,2);n=size(f,1);w=zeros(n,n); for i=1:ma=find(f(:,i)=0);if f(a(1),i)=1 w(a(1),a(2)=1;else w(a(2),a(1

13、)=1;endend elsefprint(please imput the right value of f);end w;第二讲：最短路问题程序一：dijkstra算法（计算两点间的最短路）function l,z=dijkstra(w)n = size (w,1); for i = 1 :nl(i)=w(1,i); z(i)=0;end i=1;while il(j)+w(j,i)l(i)=l(j)+w(j,i); z(i)=j-1;if jii=j-1; endendendi=i+1;end程序二：floyd 算法（计算任意两点间的最短距离）function d,r=floyd(a)n

14、=size(a,1); d=a;for i=1:nfor j=1:nr(i,j)=j;endend r;for k=1:nfor i=1:nfor j=1:nif d(i,k)+d(k,j)d(i,j)d(i,j)=d(i,k)+d(k,j); r(i,j)=r(i,k);endendendend程序三：n2short.m 计算指定两点间的最短距离function p u=n2short(w,k1,k2)n=length(w);u=w;m=1;while mu(i,m)+u(m,j)u(i,j)=u(i,m)+u(m,j);endendendm=m+1;endu=u(k1,k2);p1=zer

15、os(1,n); k=1;p1(k)=k2;v=ones(1,n)*inf; kk=k2;while kk=k1for i=1:nv(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 k=1;endendwrow=find(p1=0);for j=length(wrow):-1:1 p(k)=p1(wrow(j); k=k+1;end p;程序四、n1short.m(计算某点到其它所有点的最短距离)functionpm d=n1short(w,k)n=size(w,1);d=zeros(1,n); for i=1

16、:np 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 dt1dt2d=dt1;p=p1 p2(2

17、:length(p2) p3(2:length(p3); elsed=dt1;p=p4 p5(2:length(p5) p6(2:length(p6);end p;d;第三讲：最小生成树程序一：最小生成树的kruskal算法function t c=krusf(d,flag)if nargin=1n=size(d,2); m=sum(sum(d=0)/2; b=zeros(3,m);k=1;for i=1:nfor j=(i+1):nif d(i,j)=0b(1,k)=i;b(2,k)=j;b(3,k)=d(i,j); k=k+1;end elseendendendb=d;n=max(max(

18、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:mif 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:nif t(j)=tmaxt(j)=tmin;endendendif k=nbreak;endend t;c;程序二：最小生成树的prim算法function t c=primf(a)l=length(a); a(

19、a=0)=inf; k=1:l; listv(k)=0; listv(1)=1; e=1;while (ea(i,j) min=a(i,j);b=a(i,j); s=i;d=j;endendendendlistv(d)=1; distance(e)=b; source(e)=s; destination(e)=d;e=e+1;endt=source;destination; for g=1:e-1c(g)=a(t(1,g),t(2,g);end c;另外两种程序最小生成树程序1（prim 算法构造最小生成树）a=inf 50 60 inf inf inf inf;50 inf inf 65 4

20、0 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)-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

21、;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)loop temp=min(data(3,:); flag

22、=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.m functi

23、on 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:nif mod(a(i),2)=1 m=m+1;endendif m=0fprintf(there is not exit euler path.n) t=0;c=0;endif m=0vet=1; flag=0;t1=find(matr(vet,:)=1); for i

24、i=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 flaggflagg 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:edsc=c+d(t(1,g),t(2,g);endendendendendflagg=0; break;functionflag ed=edf(matr,e

25、ds,vexs,ed,tem) flag=1;for i=2:edsdvex f=flecvexf(matr,i,vexs,eds,ed,tem); if f=1flag=0; break;endif dvex=0ed(:,i)=vexs(1,i) dvex; vexs(1,i+1)=dvex; matr(vexs(1,i+1),vexs(1,i)=0;elsebreak;endendfunction dvex f=flecvexf(matr,i,vexs,eds,ed,temp) f=0;edd=find(matr(vexs(1,i),:)=1); dvex=0;dvex1=;ded=;if

26、 length(edd)=1 dvex=edd;elsedd=1;dd1=0;kkk=0; for kk=1:length(edd)m1=find(vexs=edd(kk); if sum(m1)=0dvex1(dd)=edd(kk); dd=dd+1;dd1=1; elsekkk=kkk+1;endendif kkk=length(edd) tem=vexs(1,i)*ones(1,kkk); edd1=tem;edd;for l1=1:kkklt=0;ddd=1; for l2=1:edsif edd1(1:2,l1)=ed(1:2,l2) lt=lt+1;endendif lt=0ded

27、(ddd)=edd(l1); ddd=ddd+1;endendendif templength(dvex1) & temp=length(ded) dvex=ded(temp);elsef=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;4126;n=size(v,1); subplot

28、(1,2,1) hold on;plot (v(:,1),v(:,2),*); %描点for i=1:nstr1=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:nd(i,j)=sqrt(v(i,1)-v(j,1)2+(v(i,2)-v(j,2)2);endend d2=0;for i=1:nif i3for m=4:n+1for i=1:(m-3)for

29、 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):jc1(k)=c(j+i+1-k);endendendendend c1(j+1):m)=c(j+1):m);elseif n=3if nfloor(a(1)/n) t2=floor(a(1)/n)+1;elset2=floor(a(1)/n);end j;end j(t1,t2)=1,j(t2,t1)=1;w(t1,:)=0;w(t2,:)=0;w(:,t1)=0;w(:,t2)=0;程序二：匈

30、牙利算法（完美匹配算法,包括三个文件fc01,fc02,fc03）function e,s=fc01(a,flag)if nargin=1 flag=0;end b=a;if flag=0cmax=max(max(b); b=cmax-b;end m=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);end d=(b=0);e,total=fc02(d); while total=m(1)b=fc03(b,e);d=(b=0);e,total=fc02(d);end inx

31、=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); while t=0s,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=

32、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);endfunction b=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; while t=0tp=sum(p+q); inp=find(p=1); n=size(inp); for i=1:n(1)inq=find(b(inp(i),:)

33、=0); q(inq)=1;end inp=find(q=1); n=size(inp); for i=1:n(1)if all(e(:,2)-inp(i)=0inq=find(e(:,2)-inp(i)=0); p(e(inq)=1;endendtq=sum(p+q); t=tq-tp;endinp=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;运行以下程序求其最大解：输入矩阵a，然后输入t,m=fc01(a)运行以

34、下程序求其最小解：输入矩阵a，然后输入t,m=fc01(a，1)匈牙利算法的另一程序匈牙利算法的 matlab 程序代码如下：m=5;n=5;a=0 1 1 0 011011011000110000011;m(m,n)=0;for(i=1:m)for(j=1:n)if(a(i,j)m(i,j)=1;break;end;end %求初始匹配mif(m(i,j)break;end;end %获得仅含一条边的初始匹配mwhile(1)for(i=1:m)x(i)=0;end %将记录x中点的标号和标记* for(i=1:n)y(i)=0;end %将记录y中点的标号和标记* for(i=1:m)pd

35、=1; %寻找x中m的所有非饱和点for(j=1:n)if(m(i,j)pd=0;end;endif(pd)x(i)=-n-1;end;end %将x中m的所有非饱和点都给以标号0和标记*, 程序中用n+1 表示0 标号, 标号为负数时表示标记* pd=0;while(1)xi=0;for(i=1:m)if(x(i)1)k=k-1; for(j=1:k)pdd=1;for(i=1:m)if(m(i,yy(j)x(i)=-yy(j);pdd=0;break;end;end%将yj 在m中与之邻接的点xk (即xkyjm), 给以标号j 和标记*if(pdd)break;end;end if(pd

36、d)k=1;j=yy(j); %yj 不是m的饱和点while(1)p(k,2)=j;p(k,1)=y(j);j=abs(x(y(j); %任取m的一个非饱和点yj, 逆向返回if(j=n+1)break;end %找到x中标号为0 的点时结束, 获得m-增广路pk=k+1;end for(i=1:k)if(m(p(i,1),p(i,2)m(p(i,1),p(i,2)=0; %将匹配m 在增广路p 中出现的边去掉else m(p(i,1),p(i,2)=1;end;end %将增广路p 中没有在匹配m 中出现的边加入到匹配m中break;end;end;endif(pd)break;end;e

37、nd %假如x中所有有标号的点都已去掉了标记*, 算法终止m %显示最大匹配m, 程序结束程序3kuhn-munkres算法（即赋权完备二元图的最佳匹配程序）function kk=kexingdian(a)%求赋权完备二元图最佳匹配a=4 5 5 1;2 2 4 6;4 2 3 3;5 0 2 1; %a 为邻接矩阵n=length(a); for(i=1:n)l(i,1)=0;l(i,2)=0;endfor(i=1:n)for(j=1:n)if(l(i,1)l(s(i),1)+l(j,2)-a(s(i),j)al=l(s(i),1)+l(j,2)-a(s(i),j);end;end;end

38、for(i=1:jss)l(s(i),1)=l(s(i),1)-al;end %调整可行点标记for(j=1:jst)l(t(j),2)=l(t(j),2)+al;end %调整可行点标记for(i=1:n)for(j=1:n) %生成子图 glif(l(i,1)+l(j,2)=a(i,j)gl(i,j)=1;else gl(i,j)=0;end m(i,j)=0;k=0;end;endii=0;jj=0; for(i=1:n)for(j=1:n)if(gl(i,j)ii=i;jj=j;break;end;endif(ii)break;end;end %获得仅含 gl 的一条边的初始匹配 mm

39、(ii,jj)=1;breakelse %nl(s)tfor(j=1:jsn)pd=1;% 取 ynl(s)t for(k=1:jst) if(t(k)=nls(j)pd=0;break;end;end if(pd)jj=j;break;end;endpd=0;%判断y 是否为 m 的饱和点for(i=1:n)if(m(i,nls(jj)pd=1;ii=i;break;end;end if(pd)jss=jss+1;s(jss)=ii;jst=jst+1;t(jst)=nls(jj);%s=sx,t=tyelse % 获 得 gl 的 一 条 m- 增 广 路 , 调 整 匹 配 m for(

40、k=1:jst)m(s(k),t(k)=1;m(s(k+1),t(k)=0;endif(jst=0)k=0;endm(s(k+1),nls(jj)=1;break;end;end;end;end maxzjpp=0;for(i=1:n)for(j=1:n)if(m(i,j)maxzjpp=maxzjpp+a(i,j);end;end;end m %显示最佳匹配 mmaxzjpp %显示最佳匹配m 的权, 程序结束第六讲：最大流最小费用问题程序一：2f算法(ford-fulkerson算法)，求最大流%c=0 5 4 3 0 0 0 0;0 0 0 0 5 3 0 0;0 0 0 0 0 3 2

41、 0;0 0 0 0 0 0 2 0;%0 0 0 0 0 0 0 4;0 0 0 0 0 0 0 3;0 0 0 0 0 0 0 5;0 0 0 0 0 0 0 0 function f wf=fulkersonf(c,f1)%c表示容量%f1表示当前流量，默认为0%f表示最大流?%wf表示最大流的流量n=length(c); if nargin=1;f=zeros(n,n); elsef=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

42、(j=1:n)if (no(j)=0 & f(i,j)d(i)d(j)=d(i);endelseif (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);endendendendendif (no(n)|pd) break;endendif (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(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