图论算法及matlab程序的三个案例

图论实验三个案例单源最短路径问题Dijkstra算法Dijkstra算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。设卜是图中的一个顶点，记/(”为顶点/到源点看的最短距离，7匕，匕£丫，若(斗，匕)右石，记匕到与的权%=8。Dijkstra算法：①S={匕}/(匕)=0；Vv^V-fvJ/(v)=ooy=i5=V-{v1}.②停止，否则转③；③/(v)=nun{/(v),J(vpv)} Vv€J.④存在心］,使"％)=n1m"")},vg5.⑤s=sU{%i},s=s-{匕+j,j=j+i,转②；实际上，Dijkstra算法也是最优化原理的应用：如果匕匕…匕是从匕到匕的最短路径，则匕匕…匕t也必然是从匕到匕t的最优路径。在下面的MATLAB实现代码中，我们用到了距离矩阵，矩阵第/行第/行元素表示顶点匕到与的权％,若匕到「无边，则％=®lmax,其中小它是MATLAB常量，表示最大的实数+308)。functionre=Dijkstra(ma)%用Dijkstra算法求单源最短路径睛俞入参量ma是距离矩阵睛俞出参量是一个三行n歹豚巨阵，每列表示顶点号及顶点到源的最短距离和前顶点"size(ma,1);%得到距离矩阵的维数s=ones(1fn);s(1)=0;%标记集合S和S的补r=zeros(3,n);r(1,:)=1:n;r(2,2:end)二realmax;%初始化fori=2:n;%控制循环次数mm=reaImax;forj:find(s=0);%集合S中的顶点fork二吊次($二二1);%集合5补中的顶点if(r(2,j)+ma(jFk)<r(2,k))r(2,k)=r(2,j)+ma(j,k);r(3,k)=j;endif(mm>r(2,k))mm=r(2,k);t=k;endendends(1,t)=0;%找到最小的顶点加入集合Sendre=r;动态规划求解最短路径动态规划是美国数学家RichardBelIman在1951年提出来的分析一类多阶段决策过程的最优化方法，在工程技术、工业生产、经济管理、军事及现代化控制工程等方面均有着广泛的应用。动态规划应用了最佳原理：假设为了解决某一优化问题，需要依次作出"个决策如若这个决策是最优的，对于任何一个整数4,1＜依〃，不论前面〃个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即也是最优的。如图1,从4点要铺设一条管道到七点，中间必须要经过5个中间站，第一站可以在｛4,4｝中任选一个，第二、三、四、五站可供选择的地点分别是:(4,4,4,福，(4,4,4。｝,14,4，4｝,(人，4J。连接两地管道的距离用连线上的数字表示，要求选一条从4到46的铺管线路，使总距离最短。囱1BT*堪的笞潜囱解决此问题可以用穷举法，从4到公有48条路径，只须比较47次，就可得到最短路径为：4T4T4T4T42T45T4外最短距离为18。也可以使用Dijkstra算法。这里，我们动态规划解决此问题。注意到最短路径有这样一个特性，即如果最短路径的第〃站通过P*,则这一最短路径在由P,出发到达终点的那一部分路径，对于始点为P*到终点的所有可能的路径来说,必定也是距离最短的。根据最短路径这一特性,启发我们计算时从最后一段开始,从后向前逐步递推的方法，求出各点到人的最短路径。在算法中，我们用数组六元数组ss表示中间车站的个数(4也作为中间车站)，用距离矩阵path表示该图。为简便起见，把该图看作有向图，各边的方向均为从左到右，则path不是对称矩阵,如path(12,14)=5,而path(14,12)=0(用0表示不通道路)。用3，16矩阵spath表示算法结果，第一行表示结点序号，第二行表示该结点到终点的最短距离，第三行表示该结点到终点的最短路径上的下一结点序号。下面给出MATLAB实现算法。function[scheme]二ShortestPath(path,ss)%利用动态规划求最短路径%path是距离矩阵,ss是车站个数n=size(path,1);%结点个数scheme二zeros(3,n);先构造结果矩阵scheme。，：)=1:n;%设置结点序号scheme(2,1:n-1)=reaImax;%预设距离值k=n-1;*记录第一阶段结点最大序号fori=size(ss,2) :1;%控制循环阶段数forj=k：-1:(k-ss(i)+1)；%当前阶段结点循环fort=find(path。，：)>0);%当前结点邻接结点ifpath(jrt)+scheme(2rt)<scheme(2rj)scheme(2,j)=path(j,t)+scheme(2,t);scheme(3,j)=t;endendendk二k-ss(i);移入下一阶段end先在MATLAB命令窗口中构造距离矩阵path,再输入：»ShortestPath(path,ss)得到以下结果：1 2 3 4 5 6 7 8 9 1011121314151618131613109 127 6 8 7 5 9 4 3 0

2 5 6 8 8 9 1012121214151516160将该结果表示为图，即为图1粗线所示。棋盘覆盖问题问题的提出在一个》、2人•个方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一特殊方格，且称该棋盘为一特殊的棋盘。如图1就是当攵=3时的特〔■IIIb们要用图2所示4种不同形态的L形骨牌覆盖一个不得重叠覆盖。图1当仁3时的特殊棋盘(b)(c)图1当仁3时的特殊棋盘(b)(c)(d)囹24种不同形木的L型曾相问题的分析易知，用到的L型骨牌个数恰为（邛-1）/3。利用分治策略，我们可以设计出解棋盘覆盖问题的一个简捷的算法。当%>0时，我们将2*x2人棋盘分割为4个2^x21子棋盘如图3两粗实线所7J\o图3棋盘分割7J\o图3棋盘分割图4关键结点特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，我们可以用一个L型骨牌覆盖

这3个较小棋盘的会合处，如图4中央L型骨牌所示，这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为1x1棋盘。算法的MATLAB实现首先特殊方格在棋盘中的位置可以用一个1x2的数组sp表示；对于图2所示的4种L型骨牌，可用数字1,2,3,4表示；对于特殊棋盘的骨牌覆盖表示，只须注意到图4所示的关键点，对每个关键点，给定一种L型骨牌，就能覆盖整个棋盘，所以对于丁x2人的特殊棋盘的骨牌覆盖，可用一个（2"-1）”2'-1）的矩阵表示。按照这种思想，图4的矩阵表示为：仁4,特殊方格位置为：[1,4]覆盖矩阵为:1仁4,特殊方格位置为：[1,4]覆盖矩阵为:1040104044003000440030100020203000300030402030203下面是在MATLAB中的棋盘覆盖实现程序。functionre=chesscover(k,sp)%解决棋盘的覆盖问题%棋盘为2、*2为，sp为特殊方格的棋盘位置globaIcovermatrixcovermatrix=zeros(2'k"1,2'k-1);evenl: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;eIsei=even1+even2+1;endtempfun(1f1rkr[sp(1,1)-evenl,sp(1,2)-even2,i]);re=covermatrix;functiontempfun(top,Ieft,k,tp)%子函数,tp为转换后特殊方格在棋盘网络的相对位置globaIcovermatrixifk=1switchtp(1,3)covermatrix(tp(1,1)ftp(1r2))=3;covermatrix(tp(1f1)Ttp(1r2))=4;covermatrix(tp(1T1)Ttp(1r2))=1;covermatrix(tp(1T1)Ttp(1r2))=2;endeIsehaIf=2"(k-1);i=top+haIf-1;j=Ieft+haIf-1;iftp(UXiiftp(1,2)<j%特殊方格在左上covermatrix(i,j)=3;%添加类型为3的L型骨牌tempfun(top,Ieft,k-1,tp);tempfun(top,Ieft+haIfrk-1,[iT,j+1,4]);tempfun(top+haIf,Ieft+haIf,k-1r[i+1,j+1,1]);tempfun(top+haIftleft,k-1,[i+1rj-1,2]);else%特殊方格在右上covermatrix(i,j)=4;%添加类型为4的L型骨牌10tempfun(top,Ieft,k-1,[iT,jT,3]);tempfun(top,Ieft+haIf,k-1,tp);tempfun(top+haIftIeft+haIf,k-1r[i+1,j+1r1]);tempfun(top+haIftleft,k-1,[i+1rj-1,2]);endeIseif 特殊方格在右下covermatrix(i,j)=1;%添加类型为3的L型骨牌tempfun(top,Ieft,k-1,[i-1,j-1,3]);tempfun(top,Ieft+haIfrk-1,[iT,j+1,4]);tempfun(top+haIf,Ieft+haIf,k-1,tp);tempfun(top+haIftleft,k-1,[i+1rj-1,2]);eIse%特殊方格在左下covermatrix(i,j)=2;%添加类型为4的L型骨牌tempfun(top,Ieft,k-1,[i-1,j-1,3]);tempfun(top,Ieft+haIf,k-1,[iT,j+1,4]);11tempfun(top+haIf,left+haIf,k-1r[i+1,j+1,1]);tempfun(top+haIf,Ieft,k-1,tp);endendend在MATLAB命令窗口中输入指令chesscover(3,[1,4])将会得到如上面矩阵一样的结果。结合VC++,利用MATLAB引擎库函数，可以给出了棋盘覆盖的图形最优树的应用实例问题的提出已知某通信系统在通信联络中只可能出现8种字符，其概率分别为，，，，，，,试设计一种编码，使得信息包长度达到最小。问题的分析12ASCII码是用8位（一个字节）表示一个字符，这种表示方法方便，易于理解,是计算机系统中常用的字符表示方法。在信息传输领域，可能有些字符出现的频率非常高，而有些字符出现的频率很低，若依然用此方法表示数据，则显得过于庞大，如果用不定长编码表示字符，频率出现高的字符用较短的编码表示，频率出现低的字符用较长的编码表示，则可以使得数据量大大减少。比如AAAABBBAAABBBBCCCCCCBBB,用ASCII码表示占用184位,若用00表示C,01表示A,1表示B,则该字串占用位数为36,压缩率达到%,这种编码称为哈夫曼编码。当然也可用其它方式压缩数据，例如上面字符串写成4A3B3A4B6c3B,而达到压缩数据的目的。哈夫曼树的构造要构造哈夫曼编码，需要构造哈夫曼树（即最优树）。哈夫曼最早给出了一个带有一般规律的算法，俗称哈夫曼算法。现叙述如下：①根据给定的〃个概率（或频率）构造一个集合/川"人同时这〃个值对应树T的"个结点，置，=〃+1。②在集合厂中选择两个最小的值求和作为力加入集合厂中；在树T中构造一结点，使得该结点是两最小值对应结点的父结点。③在集合片中删除两最小值，并置i=i+④重复②和③，直到或集合厂只有一个元素为止。这样形成的一棵树就是哈夫曼树（最优树）。上面所提到的字符串和题目给出的概率所形成的哈夫曼树分别如图1和图2（为方便起见，每个概率值乘上了100）。13

A用MATLAB实现哈夫曼算法在A用MATLAB实现哈夫曼算法在MATLAB中实现哈夫曼算法,可用一个5xQ〃-1）的矩阵来表示哈夫曼树,该矩阵的含义如表6-3-3所示。表1哈夫曼算法数据结构字符123452个1序号概率14父结点序号左右子树标志0表示左子树1表示右子树是否在集合尸1在集合尸0不在集合尸下面给出哈夫曼树的生成算法：functionhtree=HuffmanTree(pro)舟构造哈夫曼树%pro为一概率向量n=size(pro,2);先得到字符个数tree=ones(6,2*n-1);%构造树数据结构treed,:)=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);%循环控制[I,r]=findminval(tree);%找到集合中两个最小的值的序号tree(2,i)=tree(2,l)+tree(2,r);%得到父结点概率值tree⑸i)=1;%设置新构造结点在集合中15tree(3,I)=i;tree⑶r)=i;%设置父结点序号tree(4,I)=0;tree(4,r)=1;%设置左右标志tree(5,I)=0;tree⑸r)=0;%设置不在集合中tree(6,l)=i-n;tree(6,r)=i-n;%记录该次删除的结点对顺序endhtree=tree;function[Irr]=findminvaI(tree)s=find(tree⑸：)二二1);ifsize(s,2)<2error('Errorinput!1);endfirval=reaImax;secval=reaImax;fori=s;iffirval>tree(2,i)ifsecvaI>firvaIsecond=first;s