图与网络模型实验

图与网络模型实验第1页/共26页图与网络模型实验第2页/共26页第3页/共26页第4页/共26页第5页/共26页第6页/共26页第7页/共26页第8页/共26页第9页/共26页第10页/共26页2023/3/10a=zeros(6);%邻接矩阵初始化a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;a(2,3)=15;a(2,4)=20;a(2,6)=25;a(3,4)=10;a(3,5)=20;a(4,5)=10;a(4,6)=25;a(5,6)=55;a=a;b=sparse(a)

h=view(biograph(b,[],'ShowArrows','off','ShowWeights','off'))第11页/共26页实验项目名称：

图论模型MATLAB软件预处理实验目的与原理：掌握图与网络在计算机中数据存取方法，将图与网络转化为领接矩阵、稀疏矩阵等多种方法，矩阵的各种读写方式。第12页/共26页2023/3/10实验内容与步骤：渡河游戏

一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。第13页/共26页2023/3/10最短路问题定义：1）人—M（Man），狼—W（Wolf），羊—G（Goat），草—H（Hay）2）点——vi

表示河岸的状态3）边——ek

表示由状态vi

经一次渡河到状态vj

4）权——边ek

上的权定为1我们可以得到下面的加权有向图第14页/共26页2023/3/10最短路问题状态说明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G)此游戏转化为在下面的二部图中求从v1

到u1

的最短路问题。v1v2v3v4v5u5u4u3u2u1第15页/共26页根据题意，人不在场时，狼要吃羊，羊要吃菜，因此，人不在场时，不能将狼与羊，羊与蔬菜留在河的任一岸。例如，状态（0，1，1，0）表示人和菜在对岸，而狼和羊在此岸，这时人不在场狼要吃羊，因此，这个状态是不可行的。第16页/共26页通过穷举法将所有可行的状态列举出来，可行的状态有（1，1，1，1），（1，1，1，0），（1，1，0，1），（1，0，1，1），（1，0，1，0），（0，1，0，1），（0，1，0，0），（0，0，1，0），（0，0，0，1），（0，0，0，0）可行状态共有十种。每一次的渡河行为改变现有的状态。现构造赋权图

，其中顶点集合

中的顶点（按照上面的顺序编号）分别表示上述十个可行状态，当且仅当对应的两个可行状态之间存在一个可行转移时两顶点之间才有边连接，并且对应的权重取为1，当两个顶点之间不存在可行转移时，可以把相应的权重取为inf

。第17页/共26页因此问题变为在图

中寻找一条由初始状态（1，1，1，1）出发，经最小次数转移达到最终状态（0，0，0，0）的转移过程，即求从状态（1，1，1，1）到状态（0，0，0，0）的最短路径。这就将问题转化成了图论中的最短路问题。

该题的难点在于计算邻接矩阵，由于摆渡一次就改变现有的状态，为此再引入一个四维状态转移向量，用它来反映摆渡情况。用1表示过河，0表示未过河。例如，（1，1，0，0）表示人带狼过河。状态转移只有四种情况，用如下的向量表示（1，0，0，0），（1，1，0，0），（1，0，1，0），（1，0，0，1）。第18页/共26页第19页/共26页clc,cleara=[1111;1110;1101;1011;10100101;0100;0010;0001;0000];%每一行是一个可行状态b=[1000;1100;1010;1001];%每一行是一个转移状态w=zeros(10);%邻接矩阵初始化fori=1:9forj=i+1:10fork=1:4iffindstr(mod(a(i,:)+b(k,:),2),a(j,:))w(i,j)=1;endendendendw=w';%变成下三角矩阵[i,j,v]=find(w);%找非零元素c=sparse(i,j,v,10,10)%构造稀疏矩阵[x,y,z]=graphshortestpath(c,1,10,'Directed',false)%该图是无向图h=view(biograph(c,[],'ShowArrows','off','ShowWeights','off'));Edges=getedgesbynodeid(h);%提取句柄h中的边集set(Edges,'LineColor',[000]);%为了将来打印清楚，边画成黑色set(Edges,'LineWidth',1.5);%线型宽度设置为1.5第20页/共26页第21页/共26页第22页/共26页clc,cleara=zeros(7);a(1,2)=4;a(1,3)=2;a(2,3)=3;a(2,4)=2;a(2,5)=6;a(3,4)=5;a(3,6)=4;a(4,5)=2;a(4,6)=7;a(5,6)=4;a(5,7)=8;a(6,7)=3;b=sparse(a);%构造稀疏矩阵，这里给出构造稀疏矩阵的另一种方法[x,y,z]=graphshortestpath(b,1,7,'Directed',true,'Method','Dijkstra')%Directed是有向的h=view(biograph(b,[],'ShowArrows','on','ShowWeights','on'))第23页/共26页第24页/共26页2023/3/10最短路问题软件求解（1）用狄克斯屈拉算法写代码（2）用逐次逼近法写代码