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

图论实验三个案例

单源最短路径问题 1.1 Dijkstra算法

Dijkstra算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。设v是图中的一个顶点，记l(v)为顶点

v到源点v1的最短距离，

Dijkstra算法：

?vi,vj?V，若

(vi,vj)?E，记vi到

vj的权

wij??。

① S?{v1},l(v1)?0；?v?V?{v1},l(v)??,i?1,S?V?{v1}； ② S??，停止，否则转③；

③

l(v)?min{l(v),d(vj,v)}，

vj?S，?v?S；

④ 存在vi?1，使l(vi?1)?min{l(v)}，v?S； ⑤ S?S?{vi?1}，S?S?{vi?1}，i?i?1，转②；

实际上，Dijkstra算法也是最优化原理的应用：如果v1v2?vn?1vn是从v1到vn的最短路径，则v1v2?vn?1也必然是从v1到vn?1的最优路径。

在下面的MATLAB实现代码中，我们用到了距离矩阵，矩阵第i行第j行元素表示顶点vi到

vj的权

wij，若vi到

vj无边，则

wij?realmax，其中realmax是

MATLAB常量，表示最大的实数(1.7977e+308)。

function re=Dijkstra(ma)

%用Dijkstra算法求单源最短路径 %输入参量ma是距离矩阵

%输出参量是一个三行n列矩阵，每列表示顶点号及顶点到源的最短距离和前顶点

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;%初始化 for i=2:n;%控制循环次数 mm=realmax;

for j=find(s==0);%集合S中的顶点 for k=find(s==1);%集合S补中的顶点 if(r(2,j)+ma(j,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;%找到最小的顶点加入集合S end re=r;

1.2 动态规划求解最短路径

动态规划是美国数学家Richard Bellman在1951年提出来的分析一类多阶段决策过程的最优化方法，在工程技术、工业生产、经济管理、军事及现代化控制工程等方面均有着广泛的应用。动态规划应用了最佳原理：假设为了解决某一优化问题，需要依次作出n个决策D1,D2,?,Dn，如若这个决策是最优的，对于任何一个整数k，1

如图1，从A1点要铺设一条管道到A16点，中间必须要经过5个中间站，第一站可以在{ A2，A3}中任选一个，第二、三、四、五站可供选择的地点分别是：{ A4，A5，A6，A7}，{ A8，A9，A10}，{ A11，A12，A13}，{ A14，A15}。连接两地管道的距离用连线上的数字表示，要求选一条从A1到A16的铺管线路，使总距离最短。

5 1 A2 3 6 A4 A5 8 6 3 A8 2 2 A11 3 5 5 A14 4 A16 A15 3 5 A1 3 A3

3 8 A6 3 7 6 A7 8 4 A9 1 2 3 3 A12 2 6 A13 6 A10 图1 可选择的管道图

解决此问题可以用穷举法，从A1到A16有48条路径，只须比较47次，就可得到最短路径为：A1→A2→A5→A8→A12→A15→A16，最短距离为18。

也可以使用Dijkstra算法。这里，我们动态规划解决此问题。注意到最短路径有这样一个特性，即如果最短路径的第k站通过Pk，则这一最短路径在由Pk出发到达终点的那一部分路径，对于始点为Pk到终点的所有可能的路径来说，必定也是距离最短的。根据最短路径这一特性，启发我们计算时从最后一段开始，从后向前逐步递推的方法，求出各点到A16的最短路径。

在算法中，我们用数组六元数组ss表示中间车站的个数(A1也作为中间车站)，用距离矩阵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,:)=1:n;%设置结点序号 scheme(2,1:n-1)=realmax;%预设距离值 k=n-1;%记录第一阶段结点最大序号 for i=size(ss,2):-1:1;%控制循环阶段数

for j=k:-1:(k-ss(i)+1);%当前阶段结点循环 for t=find(path(j,:)>0);%当前结点邻接结点 if path(j,t)+scheme(2,t)

k=k-ss(i);移入下一阶段 end

先在MATLAB命令窗口中构造距离矩阵path，再输入：>> ShortestPath(path,ss) 得到以下结果： 1

2

3

4

5

6

7

8

9 10 11 12 18 13 16 13 10 9 12 7

6

8

7

5

2

5

6

8

8

9

10 12 12 12 14 15 将该结果表示为图，即为图1粗线所示。

13 14 9

4

15 16 15 16 3

0

16 0

棋盘覆盖问题 1.1 问题的提出

kk在一个2?2个方格组成的棋盘中，若恰有一个方格与其他方格不同，则称

该方格为一特殊方格，且称该棋盘为一特殊的棋盘。如图1就是当k?3时的特殊棋盘。棋盘覆盖问题中，我们要用图2所示4种不同形态的L形骨牌覆盖一个特殊棋盘，且任何2个L型不得重叠覆盖。

图1 当k=3时的特殊棋盘

(a)

(b)

(c)

(d)

图2 4种不同形态的L型骨牌

1.2 问题的分析

k(4?1)/3。利用分治策略，我们可以设计出易知，用到的L型骨牌个数恰为

解棋盘覆盖问题的一个简捷的算法。

kkk?1k?1当k>0时，我们将2?2棋盘分割为4个2?2子棋盘如图3两粗实线所

示。

1 2 3

图3 棋盘分割

图4 关键结点

特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，我们可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如图4中央L型骨牌所示，这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为1?1棋盘。 1.3 算法的MATLAB实现

首先特殊方格在棋盘中的位置可以用一个1?2的数组sp表示；对于图2所示的4种L型骨牌，可用数字1,2,3,4表示；对于特殊棋盘的骨牌覆盖表示，只

须注意到图4所示的关键点，对每个关键点，给定一种L型骨牌，就能覆盖整个

kkkk(2?1)?(2?1)的矩阵2?2棋盘，所以对于的特殊棋盘的骨牌覆盖，可用一个

表示。按照这种思想，图4的矩阵表示为：

?1?0??4??0?1??0?k=4，特殊方格位置为：[1,4]，覆盖矩阵为：?4040102?400020??030203??003000?040302??400030?030403??

下面是在MATLAB中的棋盘覆盖实现程序。 function re = chesscover(k,sp) %解决棋盘的覆盖问题

%棋盘为2^k*2^k，sp为特殊方格的棋盘位置 global covermatrix

covermatrix=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);%判断竖直位置是否是偶数 if even1==1&&even2==0%找出找出特殊方格相对关键结点的位置 i=4; else

i=even1+even2+1;

end

tempfun(1,1,k,[sp(1,1)-even1,sp(1,2)-even2,i]); re=covermatrix;

function tempfun(top,left,k,tp)%子函数,tp为转换后特殊方格在棋盘网络的相对位置

global covermatrix if k==1

switch tp(1,3) case 1

covermatrix(tp(1,1),tp(1,2))=3; case 2

covermatrix(tp(1,1),tp(1,2))=4; case 3

covermatrix(tp(1,1),tp(1,2))=1; case 4

covermatrix(tp(1,1),tp(1,2))=2; end else

half=2^(k-1);i=top+half-1;j=left+half-1; if tp(1,1)

if tp(1,2)

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]); end else

if tp(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); end end end

在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位(一个字节)表示一个字符，这种表示方法方便，易于理解，是计算机系统中常用的字符表示方法。在信息传输领域，可能有些字符出现的频率非常高，而有些字符出现的频率很低，若依然用此方法表示数据，则显得过于庞大，如果用不定长编码表示字符，频率出现高的字符用较短的编码表示，频率出现低的字符用较长的编码表示，则可以使得数据量大大减少。比如AAAABBBAAABBBBCCCCCCBBB，用ASCII码表示占用184位，若用00表示C，01表示A，1表示B，则该字串占用位数为36，压缩率达到19.6%，这种编码称为哈夫曼编码。当然也可用其它方式压缩数据，例如上面字符串写成4A3B3A4B6C3B，而达到压缩数据的目的。 1.3 哈夫曼树的构造

要构造哈夫曼编码，需要构造哈夫曼树（即最优树）。哈夫曼最早给出了一个带有一般规律的算法，俗称哈夫曼算法。现叙述如下：

① 根据给定的n个概率（或频率）构造一个集合F?{f1,f2,?,fn}，同时这

n个值对应树T的n个结点，置i?n?1。

② 在集合F中选择两个最小的值求和作为fi加入集合F中；在树T中构造一结点，使得该结点是两最小值对应结点的父结点。

③ 在集合F中删除两最小值，并置i?i?1。

④ 重复②和③，直到i?2n?1或集合F只有一个元素为止。这样形成的一棵树就是哈夫曼树（最优树）。

上面所提到的字符串和题目给出的概率所形成的哈夫曼树分别如图1和图2(为方便起见，每个概率值乘上了100)。

0 0 23 42 0 1 23 100 1 58 1 0 29 0 1 14 15 0 1 7 8 1 10 B 13 0 1 7 A 6 C

图1

19 29 0 1 11 8 0 1 5 3 图2

1.4 用MATLAB实现哈夫曼算法

在MATLAB中实现哈夫曼算法，可用一个5?(2n?1)的矩阵来表示哈夫曼树，该矩阵的含义如表6-3-3所示。

表1 哈夫曼算法数据结构

字符 1 序号 概率 2 3 4 5 ……… 2n-1 父结点 序号 左右子0表示1表示树标志 左子树 右子树 是否在1在集0不在集合F 合F 集合F 下面给出哈夫曼树的生成算法： function htree = 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;%记录查找的结点对顺序 for i=(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;%记录该次删除的结点对顺序 end

htree=tree;

function [l,r]=findminval(tree) s=find(tree(5,:)==1); if size(s,2)<2

error('Error input!'); end

firval=realmax;secval=realmax; for i=s;

if firval>tree(2,i) if secval>firval

second=first;secval=firval;