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

图论实验的三个案例单一来源最短路径问题1.1 Dijkstra算法Dijkstra算法是求解单个源最短路径问题的贪心算法。基本想法是设置顶点集s，然后继续进行扩展此集的贪心选择。顶点属于集s，并且仅知道从源到该顶点的最短路径长度。将v设置为地物中从顶点v到源点v1的最短距离的顶点。否则就是要记住的权利。Dijkstra算法：、停止，否则转动。、存在，所以；，轮到；实际上，Dijkstra算法也应用了优化原理。从到的最短路径只能是从到的最佳路径。以下MATLAB实现代码使用了距离矩阵，矩阵I行j行元素表示顶点达到的权重，如果达到无穷大，则其中realmax是表示最大实数(1.7977e 308)的MATLAB常量：Function re=Dijkstra(ma)使用% Dijkstra算法查找单个源最短路径%输入参数ma是距离矩阵%输出参数是一个三行n列矩阵，表示顶点编号和从顶点到源的最短距离以及前一个顶点N=size(ma，1)；获取% distance矩阵的维数S=ones(1，n)；s(1)=0；%显示集s和s的补充R=zeros(3，n)；R(1，)=1:n；R (2，23360 end)=real max；初始化%For i=2:n%控制周期数Mm=realmaxfor j=find(s=0)；%集s中的顶点for k=find(s=1)；%集s补充的顶点If(r(2，j) ma(j，k)r(2，k)Mm=r(2，k)；t=k；EndEndEndS(1，t)=0；%最小的顶点查找集sEndre=r；1.2求解最短路径的动态编程是1951年美国数学家Richard Bellman提出的多层次决策过程分析的优化方法，工程技术、工业生产、经济管理、军事和现代控制项目得到了广泛应用。动态编程应用了最优原则。假设为了解决优化问题，必须依次做出n个决策，这是最佳决策，对于所有整数k，10:%当前节点相邻节点If path (j，t)方案(2，t)最短路径(path，ss)得到以下结果：1234567891011121314151618131613109127687594302568891012121214151516160将结果显示为图1中的粗线。棋盘盖问题1.1提出问题图1 k=3时的特殊主板在一个正方形组成的棋盘上，如果有不同于其他图案的图案，则该正方形称为特殊正方形，该图案称为特殊棋盘。图1是当时的专用板。在棋盘盖问题上，我们想用图2所示的4种不同形式的l形复盖特殊棋盘，任何2种l形都不能重叠。图2四种不同形式的l型骨卡(a)(b)(c)(d)1.2问题分析众所周知，使用的l型骨卡的数量是正确的。利用分割策略，我们可以设计出解决棋盘盖问题的简单算法。在K0中，将棋盘分割为四个子板，如图3中的粗实线所示。图4密钥节点123图3棋盘分割特殊复选框必须位于四个子板之一，其他三个子板不能有特殊复选框。为了将这三个不特别的棋盘转换成特殊的棋盘，如图4的中央l-球门板所示，三个每一个棋盘上复盖着l-球门板的正方形成为该棋盘的特殊正方形，从而将原来的问题转换成四个小棋盘盖问题。递归使用此分割，直到棋盘简化为棋盘。1.3算法的MATLAB实现首先，可以用一个阵列sp表示棋盘上特殊棋盘格的位置；图2中所示的4个l-骨牌可以用数字1，2，3，4表示。对于特定棋盘的骨板盖表示，只要注意图4中显示的键，每个键就可以给定一个l型骨板，复盖整个棋盘，因此，对于的特殊板的骨板盖，可以用一个矩阵表示。根据这个想法，图4中的矩阵表示为：K=4，特殊棋盘格位置为1，4，嵌套矩阵为：以下是MATLAB的主板复盖实现程序：Function re=chesscover(k，sp)解决主板% coverage问题%棋盘为2 k * 2 k，sp是特殊棋盘格的棋盘位置Global covermatrixCover matrix=zeros (2 k-1，2k-1)；Even 1=floor (sp (1，1)/2) * 2=sp (1，1)；%确定水平位置是否为偶数Even 2=floor (sp (1，2)/2) * 2=sp (1，2)；%确定垂直位置是否为偶数查找If even1=1even2=0%特殊棋盘格的相对关键节点位置I=4；ElseI=事件1事件2 1；EndTempfun (1，1，k，sp (1，1)-even 1，sp (1，2)-even 2，I)；Re=covermatrixFunction tempfun (top，left，k，TP)%子函数，TP是转换后电路板网络上特殊棋盘格的相对位置Global covermatrixIf k=1交换机tp(1，3)案例1Covermatrix(tp(1，1)，tp(1，2)=3；案例2Covermatrix(tp(1，1)，tp(1，2)=4；案例3Covermatrix(tp(1，1)，tp(1，2)=1；事例4Covermatrix(tp(1，1)，tp(1，2)=2；EndElsehalf=2(k-1)；I=top half-1；j=left half-1；If tp(1，1)j%特殊复选框位于右下角盖子矩阵(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%特殊正方形位于左下角盖子矩阵(I，j)=2；添加% 4类型的l-gold卡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)将得到与上述矩阵相同的结果。与VC结合使用，MATLAB引擎库函数可以提供棋盘盖图形最佳树的应用实例1.1提出问题众所周知，通信系统只能在通信线路上出现8个字符，概率分别为0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，设计了将数据包长度最小化的编码。1.2问题分析ASCII代码以8位(1字节)表示一个字符，这种显示方法方便易懂，是计算机系统中常用的字符显示方法。在信息传输区域，某些字符发生得非常频繁，而某些字符可能以极低的频率出现，如果使用此方法继续表示数据，则可能过于庞大，以无限长的编码显示字符，以较短的编码显示高频率字符，以较长的编码显示低频率字符，则可以大大减少数据量。例如，如果AAAABBBAAABBBBCCCCCCBBB占用184位作为ASCII代码，用c，01表示a，1表示b，则此字符串占用36位，压缩率占用19.6%，这种编码称为仅huff编码。要压缩数据，还可以使用其他方法(例如4A3B3A4B6C3B)压缩数据。1.3霍夫曼树结构要配置Huffman编码，必须配置Huffman树(即最优树)。赫夫曼首先提出了一种有一般规律的算法，称为赫夫曼算法。以下是：根据给定的n个概率(或频率)组织集合，这n个值对应于树t中的n个节点。从集f中选择要添加到集f的两个最小值的总和。在