图论matlab模板程序

1、图论matlab模板程序第一讲：图论模型程序一：可达矩阵算法%根据邻接矩阵 A (有向图)求可达矩阵P (有向图)function P=dgraf(A)n=size(A,1);P=A;for i=2:nP=P+AAi;endP(P-=0)=1; % 将不为0的元素变为1P;程序二：无向图关联矩阵和邻接矩阵互换算法F表示所给出的图的相应矩阵W表示程序运行结束后的结果f=0表示把邻接矩阵转换为关联矩阵f=1表示把关联矩阵转换为邻接矩阵%无向图的关联矩阵和邻接矩阵的相互转换function W=incandadf(F,f)if f=0m=sum(sum(F)/2; % n=size(F,1);邻接矩

2、阵转换为关联矩阵 计算图的边数W=zeros(n,m); k=1;fori=1:nfor j=i:nifF(i,j)=0W(i,k)=1;给边的始点赋值为1endelseifW(j,k)=1;k=k+1;endendf=1 %给边的终点赋值为1关联矩阵转换为邻接矩阵m=size(F,2);n=size(F,1);W=zeros(n,n);for i=1:m存在边,那么邻接矩阵的对应值为1a=find(F(:,i)=0);W(a(1),a(2)=1; %W(a(2),a(1)=1;end else)；fprint( 'Please imput the right value of f&#

3、39; endW;程序三：有向图关联矩阵和邻接矩阵互换算法%有向图的关联矩阵和邻接矩阵的转换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:nif 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

4、),a(2)=1; % elseW(a(2),a(1)=1; % end邻接矩阵转换为关联矩阵由i发出的边,有向边的始点关联矩阵始点值为1关联矩阵终点值为-1关联矩阵转换为邻接矩阵有向边的两个顶点有向边由a(1)指向a(2)有向边由a(2)指向a(1)endelse);fprint( 'Please imput the right value of f' endW;第二讲：最短路问题程序0:最短距离矩阵W表示图的权值矩阵D表示图的最短距离矩阵%连通图中各项顶点间最短距离的计算function D=shortdf(W)%对于W(i,j),假设两顶点间存在弧,那么为弧的权值,否那么

5、为 inf ；当1弓 时W(i,j)=0n=length(W);D=W;m=1;while m<=nfor i=1:nfor j=1:nif D(i,j)>D(i,m)+D(m,j)D(i,j)+ D(i,m)+D(m,j); %距离进行更新endendendm=m+1;endD;程序一：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

6、(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);endend end end程序三：n2short.m计算指定两点间的最短距离 funct

7、ion P u=n2short(W,k1,k2) n=length(W);U=W;m=1;while m<=nfor i=1:nfor j=1:nif U(i,j)>U(i,m)+U(m,j)U(i,j)=U(i,m)+U(m,j);endendendm=m+1;endu=U(k1,k2);P1=zeros(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;endendendk=1;wrow

8、=find(P1=0);for j=length(wrow):-1:1P(k)=P1(wrow(j);k=k+1;endP;程序四、n1short.m(计算某点到其它所有点的最 短距离)function Pm D=n1short(W,k)n=size(W,1);D=zeros(1,n);for i=1: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,t

9、2);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<dt2d=dt1;P=p1 p2(2:length(p2) p3(2:length(p3);elsed=dt1;p=p4 p5(2:length(p5) p6(2:length(p6);endP;d;第三讲：最小生成树程序一：最小生成树的Kruskal算法 function T c=krusf(d,flag) if nargin=1n=

10、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)=0 b(1,k)=i;b(2,k)=j; b(3,k)=d(i,j);k=k+1;end endendelseb=d;endn=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: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),

11、t(B(2,i);tmax=max(t(B(1,i),t(B(2,i); for j=1:nif t(j)=tmax t(j)=tmin;endendendif k=nbreak ;endendT;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:lif listV(i)=1 for j=1:lif listV(j)=0 & min>a(i,j) min=a(i,j);b=a(i,

12、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);endc;第四讲：Euler图和Hamilton图程序一：Fleury算法(在一个 Euler图中找出Euler环游)注：包括三个文件；fleuf1.m, edf.m, flecvexf.mfunction T c=fleuf1(d)%:必须保证是 Euler环游,否那么输出 T=0,c=0n=length(d);b=d

13、;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)=1m=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 ii=1:length(t1)ed(:,1)=vet,t1(ii);vexs(1,1)=vet;vexs(1,2)=t

14、1(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)=0T=ed;T(2,eds)=1;c=0;for g=1:edsc=c+d(T(1,g),T(2,g);endflagg=0;break ;endendendend function flag ed=edf(matr,eds,vexs,ed,tem) flag=1;for i=2:edsdvex f=flecvexf(matr,i

15、,vexs,eds,ed,tem);if f=1flag=0;break ;if 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 length(edd)=1 dvex=edd;elsedd=1;dd1=0;kkk=0;for kk=1:length(e

16、dd)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(ddd)=edd(l1);ddd=ddd+1;endendif temp<=length(dvex1)dvex=dvex1(te

17、mp);elseif temp>length(dvex1) & temp<=length(ded) dvex=ded(temp);elsef=1;endend程序二：Hamilton 改进圈算法找出比拟好的Hamilton 路function C d1= hamiltonglf(v)%d表示权值矩阵%C1示算法最终找到的Hamilton 圈.%v = 51 67;37 84;41 94;2 99;18 54;4 50;24 42;25 38;13 40;7 64;22 60;2562;18 40;41 26;n=size(v,1);subplot(1,2,1)hold on

18、;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:nfor j=1:nd(i,j尸sqrt(v(i,1)-v(j,1)A2+(v(i,2)-v(j,2)F2);endendd2=0;for i=1:nif i<nd2=d2+d(i,i+1);elsed2

19、=d2+d(n,1);end endtext(10,30,num2str(d2);n=size(d,2);C=linspace(1,n,n) 1;for nnn=1:20C1=C;if n>3for m=4:n+1for 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);endC1(j+1):m)=C(j+1):m); end end end end elseif n&l

20、t;=3 if n<=2fprint('It does not exist Hamilton circle.'); elsefprint('Any cirlce is the right answer.'); end end C=C1; d1=0;for i=1:nd1=d1+d(C(i),C(i+1);end d1;endsubplot(1,2,2); hold on;plot (v(:,1),v(:,2),'*'); %描点for i=1:nstr1='V'str2=num2str(i);dot=str1,str2;给点

21、命名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);第五讲：匹配问题及算法程序一：较大根底匹配算法function J=matgraf(W)n=size(W,1);J=zeros(n,n);while sum(sum(W)=0a=find(W=0);t1=mod(a(1),n);if t1=0t1=n;endif a(1)/n>floor(a(1)/n)t2=floor(a(1)/n)+1;elset2=floor(

22、a(1)/n);endJ(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=1flag=0;endb=a;if flag=0cmax=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);en

23、dd=(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');while t=0s,inp=sort(nump);inq=find(s);ep=inp(inq(1);inp=find(d(ep,:)

24、;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);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

25、;while t=0tp=sum(p+q);inp=find(p=1);n=size(inp);for i=1:n(1)inq=find(b(inp(i),:)=0);q(inq)=1;endinp=find(q=1);n=size(inp);for i=1:n(1)if all(e(:,2)-inp(i)=0 inq=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(in

26、p,:)=b(inp,:)-cmin;b(:,inq)=b(:,inq)+cmin;第六讲：最大流最小费用问题程序一：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 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)%C1示容量%f1表示当前流量,默认为 0%f表示最大流 士 i6?X?'+%wf表示最大流的流

27、量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 (j=1:n)if (No(j)=0 & f(i,j)<C(i,j)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) No(j)=-i;d(j)=f(j,i

28、);pd=0;if (d(j)>d(i) d(j)=d(i);endendendendendif (No(n)|pd) break ;endendif (pd)break ;enddvt=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;endif (No(t)=1)for (i=1:n) No(i)=0;d(i)=0;endbreakendt=No(t);end wf=0; for (j=1:n) wf=wf+f(1,j); end f; wf;程序二：Busacker-Gowan 算法(求最大流最小 费用) %C=0 15 16 0 0;0 0 0 13 14;0 11 0 17 0;0 0 0 0 8;0 0 0 0 0 %b=0 4 1 0 0;0 0 0 6 1;0 2 0 3 0;0 0 0 0 2;0 0 0 0 0 %function f wf zwf=BGf(C,b) %C1示弧容量矩阵 %b表示弧上单位流量的费用 %f表示