MATLAB数学建模与仿真（第2版·微课视频版）程序代码 第15章-图论算法及MATLAB仿真代码

计算图的可达矩阵functionP=dgraf(A)n=size(A,1);P=A;%计算矩阵Bnfori=2;nP=P+A^i;endP(P~=0)=1%将不为0的元素变为1P;运行以下程序：>>A=['0111';'1011';'1101';'1110'];>>P=dgraf(A)%调用函数dgraf运行结果如下:P=1111111111111111连通图中各顶点间最短距离的计算functionD=shortdf(W)%对于W(i,j),若两顶点间存在弧,则为弧的权值,否则为inf;当i=j时,W(i,j)=0n=length(W);D=W;m=1;whilem<=nfori=1:nforj=1:nifD(i,j)>D(i,m)+D(m,j)D(i,j)=D(i,m)+D(m,j);%距离进行更新endendendm=m+1;endD;用Dijkstra算法求单源最短路径functionre=Dijkstra(ma)%输入参量ma是距离矩阵n=size(ma,1);%得到距离矩阵的维数s=ones(1,n);s(1)=0;%标记集合S和S的补r=zeros(3,n);r(1,:)=1:n;r(2,2:end)=realmax;%初始化fori=2:n;%控制循环次数

mm=realmax;

forj=find(s==0);%集合S中的顶点

fork=find(s==1);%集合S补中的顶点

if(r(2,j)+ma(j,k)<r(2,k))

r(2,k)=r(2,j)+ma(j,k);r(3,k)=j;

end

if(mm>r(2,k))

mm=r(2,k);t=k;

end

end

end

s(1,t)=0;%找到最小的顶点加入集合Sendre=r;Floyd算法的MATLAB程序如下。%采用floyd算法计算图a中每对顶点最短路%d是矩离矩阵%r是路由矩阵n=size(a,1);d=a;fori=1:nforj=1:nr(i,j)=j;endendrfork=1:nfori=1:nforj=1:nifd(i,k)+d(k,j)<d(i,j)d(i,j)=d(i,k)+d(k,j);r(i,j)=r(i,k)endendendkdrend利用动态规划求最短路径function[scheme]=ShortestPath(path,ss)%path是距离矩阵,ss是车站个数n=size(path,1);%结点个数scheme=zeros(3,n);%构造结果矩阵scheme(1,:)=1:n;%设置结点序号scheme(2,1:n-1)=realmax;%预设距离值k=n-1;%记录第一阶段结点最大序号fori=size(ss,2):-1:1;%控制循环阶段数

forj=k:-1:(k-ss(i)+1);%当前阶段结点循环

fort=find(path(j,:)>0);%当前结点邻接结点

ifpath(j,t)+scheme(2,t)<scheme(2,j)

scheme(2,j)=path(j,t)+scheme(2,t);

scheme(3,j)=t;

end

end

end

k=k-ss(i);移入下一阶段end先在MATLAB命令窗口中构造距离矩阵path，再输入：>>ShortestPath(path,ss)得到以下结果：1234567891011121314151618131613109127687594302568891012121212151516160MATLAB中的棋盘覆盖实现程序。functionre=chesscover(k,sp)%解决棋盘的覆盖问题%棋盘为2^k*2^k，sp为特殊方格的棋盘位置globalcovermatrixcovermatrix=zeros(2^k-1,2^k-1);even1=floor(sp(1,1)/2)*2==sp(1,1);%判断水平位置是否是偶数even2=floor(sp(1,2)/2)*2==sp(1,2);%判断竖直位置是否是偶数ifeven1==1&&even2==0%找出找出特殊方格相对关键结点的位置i=4;elsei=even1+even2+1;endtempfun(1,1,k,[sp(1,1)-even1,sp(1,2)-even2,i]);re=covermatrix;functiontempfun(top,left,k,tp)%子函数,tp为转换后特殊方格在棋盘网络的相对位置globalcovermatrixifk==1 switchtp(1,3)case1covermatrix(tp(1,1),tp(1,2))=3;case2covermatrix(tp(1,1),tp(1,2))=4;case3covermatrix(tp(1,1),tp(1,2))=1;case4covermatrix(tp(1,1),tp(1,2))=2; endelse half=2^(k-1);i=top+half-1;j=left+half-1;iftp(1,1)<iiftp(1,2)<j%特殊方格在左上covermatrix(i,j)=3;%添加类型为3的L型骨牌tempfun(top,left,k-1,tp);tempfun(top,left+half,k-1,[i-1,j+1,4]);tempfun(top+half,left+half,k-1,[i+1,j+1,1]);tempfun(top+half,left,k-1,[i+1,j-1,2]);else%特殊方格在右上covermatrix(i,j)=4;%添加类型为4的L型骨牌tempfun(top,left,k-1,[i-1,j-1,3]);tempfun(top,left+half,k-1,tp);tempfun(top+half,left+half,k-1,[i+1,j+1,1]);tempfun(top+half,left,k-1,[i+1,j-1,2]);endelseiftp(1,2)>j%特殊方格在右下covermatrix(i,j)=1;%添加类型为3的L型骨牌tempfun(top,left,k-1,[i-1,j-1,3]);tempfun(top,left+half,k-1,[i-1,j+1,4]);tempfun(top+half,left+half,k-1,tp);tempfun(top+half,left,k-1,[i+1,j-1,2]);else%特殊方格在左下covermatrix(i,j)=2;%添加类型为4的L型骨牌tempfun(top,left,k-1,[i-1,j-1,3]);tempfun(top,left+half,k-1,[i-1,j+1,4]);tempfun(top+half,left+half,k-1,[i+1,j+1,1]);tempfun(top+half,left,k-1,tp);endendend在MATLAB命令窗口中输入指令>>chesscover(3,[1,4])将会得到矩阵：下面给出哈夫曼树的生成算法：functionhtree=HuffmanTree(pro)%构造哈夫曼树，pro为一概率向量n=size(pro,2);%得到字符个数tree=ones(6,2*n-1);%构造树数据结构tree(1,:)=1:(2*n-1);%填充结点序号tree(5,(n+1):end)=0;%设置结点是否在集合tree(2,1:n)=pro;%设置概率tree(6,1:end)=0;%记录查找的结点对顺序fori=(n+1):(2*n-1);%循环控制 [l,r]=findminval(tree);%找到集合中两个最小的值的序号 tree(2,i)=tree(2,l)+tree(2,r);%得到父结点概率值 tree(5,i)=1;%设置新构造结点在集合中 tree(3,l)=i;tree(3,r)=i;%设置父结点序号 tree(4,l)=0;tree(4,r)=1;%设置左右标志 tree(5,l)=0;tree(5,r)=0;%设置不在集合中 tree(6,l)=i-n;tree(6,r)=i-n;%记录该次删除的结点对顺序endhtree=tree;function[l,r]=findminval(tree)s=find(tree(5,:)==1);ifsize(s,2)<2 error('Errorinput!');endfirval=realmax;secval=realmax;fori=s; iffirval>tree(2,i)ifsecval>firvalsecond=first;secval=firval;endfirst=i;firval=tree(2,i); elseifsecval>tree(2,i)second=i;secval=