(圖論)matlab模板程序

1、第一講：圖論模型程序一：可達(dá)矩陣算法% 根據(jù)鄰接矩陣A (有向圖)求可達(dá)矩陣P (有向圖)function P=dgraf(A)n=size(A,1);P=A;for i=2:np=p+A”endp(p=0)=1; % 將不為 0 的元素變?yōu)?p;程序二：無(wú)向圖關(guān)聯(lián)矩陣和鄰接矩陣互換算法F 表示所給出的圖的相應(yīng)矩陣W表示程序運(yùn)行結(jié)束后的結(jié)果f=0 表示把鄰接矩陣轉(zhuǎn)換為關(guān)聯(lián)矩陣 f=1 表示把關(guān)聯(lián)矩陣轉(zhuǎn)換為鄰接矩陣 %無(wú)向圖的關(guān)聯(lián)矩陣和鄰接矩陣的相互轉(zhuǎn)換function W=incandadf(F,f)if f=0%m=sum(sum(F)/2; % n=size(F,1);W=zeros(n,

2、m); k=1;for i=1:nfor j=i:nif F(i,j)=0 W(i,k)=1; % W(j,k)=1; % k=k+1;endend鄰接矩陣轉(zhuǎn)換為關(guān)聯(lián)矩陣計(jì)算圖的邊數(shù)給邊的始點(diǎn)賦值為1給邊的終點(diǎn)賦值為1endelseif f=1 % 關(guān)聯(lián)矩陣轉(zhuǎn)換為鄰接矩陣m=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存在邊，則鄰接矩陣的對(duì)應(yīng)值為1elsefprint( Please imput the right value of f)endW;程序

3、三：有向圖關(guān)聯(lián)矩陣和鄰接矩陣互換算法%有向圖的關(guān)聯(lián)矩陣和鄰接矩陣的轉(zhuǎn)換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:nfor 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)=1W(a(1),a(2)=1; % else

4、W(a(2),a(1)=1; % end end else fprint(關(guān)聯(lián)矩陣轉(zhuǎn)換為鄰接矩陣鄰接矩陣轉(zhuǎn)換為關(guān)聯(lián)矩陣i 發(fā)出的邊，有向邊的始點(diǎn)關(guān)聯(lián)矩陣始點(diǎn)值為1關(guān)聯(lián)矩陣終點(diǎn)值為-1有向邊的兩個(gè)頂點(diǎn)有向邊由a(1) 指向a(2)有向邊由a(2) 指向a(1)Please imput the right value of fendW;第二講：最短路問(wèn)題程序 0：最短距離矩陣W表示圖的權(quán)值矩陣D表示圖的最短距離矩陣%連通圖中各項(xiàng)頂點(diǎn)間最短距離的計(jì)算function D=shortdf(W)%對(duì)于W(i,j), 若兩頂點(diǎn)間存在弧，則為弧的權(quán)值，否則為inf ；當(dāng) i=j 時(shí) W(i,j)=0n=le

5、ngth(W);D=W;m=1;while mD(i,m)+D(m,j)D(i,j)+ D(i,m)+D(m,j); %距離進(jìn)行更新endendendm=m+1;endD;程序一：Dijkstra 算法(計(jì)算兩點(diǎn)間的最短路)function l,z=Dijkstra(W)n = size (W,1);for i = 1 :nl(i)=W(1,i);z(i)=0;endi=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 算法(計(jì)算任意兩點(diǎn)間的最短距離)function d,r

6、=floyd(a)n=size(a,1);d=a;for i=1:nfor j=1:n r(i,j)=j;endendr;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 計(jì)算指定兩點(diǎn)間的最短距離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,k

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

8、=1:nP d=n2short(W,k,i);Pmi=P;D(i)=d;end程序五：pass2short.m( 計(jì)算經(jīng)過(guò)某兩點(diǎn)的最短距離)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:len

9、gth(p2) p3(2:length(p3);elsed=dt1;p=p4 p5(2:length(p5) p6(2:length(p6); endP;d;第三講：最小生成樹(shù)程序一：最小生成樹(shù)的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)=0 b(1,k)=i;b(2,k)=j; b(3,k)=d(i,j);k=k+1;end elseb=d;endn=max(max(b(1:2,:);m

10、=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)=tmax t(j)=tmin;endendendif k=n break ;endendT;c;程序二：最小生成樹(shù)的Prim 算法function T c=Primf(a) l=length(a); a(a=0)=inf; k=

11、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);endc;第四講：Euler 圖和 Hamilton 圖程序一：Fleury 算法(在一個(gè)Euler 圖中找出Euler 環(huán)游)注：包括三個(gè)文件；fleuf1.m, edf.m, flecvex

12、f.mfunction T c=fleuf1(d) %注：必須保證是Euler 環(huán)游，否則輸出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;end endif m=0fprintf( there is not exit Euler path.n)T=0;c=0;endif m=0vet=1;flag=0;t1=find(matr(vet

13、,:)=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 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 ;endendendendfunction flag ed=e

14、df(matr,eds,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=;de

15、d=;if 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(dd

16、d)=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表示權(quán)值矩陣%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

17、,2,1)hold on;plot (v(:,1),v(:,2),*); %描點(diǎn)for i=1:nstr1=V;str2=num2str(i);dot=str1,str2;text(v(i,1)-1,v(i,2)-2,dot); %給點(diǎn)命名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)-vO,2)A2);endendd2=0;for i=1:nif i3for m=4:n+1for i=1:(m-3)for j=(i+

18、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);endC1(j+1):m)=C(j+1):m);endendendendelseif n=3if nfloor(a(1)/n)t2=floor(a(1)/n)+1;elset2=floor(a(1)/n);endJ(t1,t2)=1,J(t2,t1)=1;W(t1,:)=0;W(t2,:)=0;W(:,t1)=0;W(:,t2)=0;endJ;程序二：匈牙利算法(完美匹配算法

19、, 包括三個(gè)文件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);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),

20、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=find(d(:,eq);nump(inp)=num

21、p(inp)-1;nump(ep)=0;t=t-sum(d(ep,:)-sum(d(:,eq)+1;d(ep,:)=0*d(ep,:);d(:,eq)=0*d(:,eq);endfunctionb=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),:)=O);q(inq)=1;endinp=find(q=1);n=si

22、ze(inp);for i=1 :n(1)if all(e(:,2)-inp(i)=0 inq=find(e(:,2)-inp(i)=0); p(e(inq)=1;endend tq=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;第六講：最大流最小費(fèi)用問(wèn)題程序一：2F 算法 (Ford-Fulkerson 算法 ) ，求最大流%C=0 5 4 3 0 0 0 0;0 0 0 0

23、 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 表示當(dāng)前流量，默認(rèn)為0%f表示最大流 士 i 6 ?X? o a -%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 (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) br