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))]; end P; d;
程序三：有向图关联矩阵和邻接矩阵互换算法
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 end elseif 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'); end W;
第二讲：最短路问题
程序一：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
第三讲：最小生成树
程序一：最小生成树的 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 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; 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
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; end u=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 end end k=1; wrow=find(P1~=0); for j=length(wrow):-1:1 P(k)=P1(wrow(j)); k=k+1; end P;
超全的图论程序
程序一：可达矩阵算法
function P=dgraf(A) n=size(A,1); P=A; for i=2:n P=P+A^i; end P(P~=0)=1; P;
程序二：关联矩阵和邻接矩阵互换算法
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 end elseif 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; end else fprint('Please imput the right value of f'); end W;
另外两种程序
最小生成树程序 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];
end T; 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; end T=[source;destination]; for g=1:e-1 c(g)=a(T(1,g),T(2,g)); end c;
程序四、n1short.m(计算某点到其它所有点的最短距离)
function[Pm D]=n1short(W,k) n=size(W,1);
D=zeros(1,n); for i=1:n [P d]=n2short(W,k,i); Pm{i}=P; D(i)=d; end
程序五：pass2short.m(计算经过某两点的最短距离)
第四讲：Euler 图和 Hamilton 图
程序一： Fleury 算法（在一个 Euler 图中找出 Euler 环游）
注：包括三个文件；fleuf1.m, edf.m, flecvexቤተ መጻሕፍቲ ባይዱ.m function [T c]=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; for i=1:n if mod(a(i),2)==1 m=m+1; end end if m~=0 fprintf('there is not exit Euler path.\n') T=0;c=0; end if 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 end
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;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=[]; while length(result)<loop temp=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)]; end index(find(index==v2))=v1; data(:,flag)=[]; index(:,flag)=[]; end result