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

运筹学算法matlab程序西北工业大学数学系2009级1.顺向Dijkstra 算法M=[ 0 5 9 Inf Inf Inf InfInf 0 Inf Inf 12 Inf InfInf 3 0 15 Inf 23 InfInf 6 Inf 0 Inf 8 7Inf 12 Inf 5 0 Inf 14Inf Inf Inf Inf Inf 0 10Inf Inf Inf Inf Inf Inf 0];first=1;last=7;[m,n]=size(M);L=zeros(1,m);symbol=zeros(1,m);direction=zeros(1,m);for i=1:mif(i~=first)L(i)=inf;enddirection(i)=first;endjudge=1;while judgefor i=1:mif(symbol(i)==0)min=L(i);temporary=i;breakendendfor i=1:mif(symbol(i)==0)if(L(i)<min)min=L(i);temporary=i;endendendk=temporary;for j=1:mif(symbol(1,j)==0)if(M(k,j)==inf)continue;elseif(L(k)+M(k,j)<L(j))L(j)=L(k)+M(k,j);direction(j)=k;endendendendsymbol(k)=1;num=0;for i=1:mif(symbol(i)==1)num=num+1;endendif(num==m)judge=0;endendp=last;arrow=zeros(1,m);arrow(1)=last;i=2;while p~=firstarrow(1,i)=direction(p);i=i+1;p=direction(p);enddistance=L(last);M=[ 0 5 9 Inf Inf Inf Inf Inf 0 Inf Inf 12 Inf InfInf 3 0 15 Inf 23 Inf Inf 6 Inf 0 Inf 8 7 Inf 12 Inf 5 0 Inf 14 Inf Inf Inf Inf Inf 0 10Inf Inf Inf Inf Inf Inf 0]; [m,n]=size(M);first=1;last=7;L=zeros(1,m);direction=zeros(1,m);symbol=zeros(1,m);for i=1:mdirection(i)=last;if(i~=last)L(i)=inf;endendjudge=1;while judgefor i=1:mif(symbol(i)==0)min=L(i);temporary=i;breakendendfor i=1:mif(symbol(i)==0)if(L(i)<min)min=L(i);temporary=i;endendendk=temporary;for i=1:mif(M(i,k)==inf)continueelseif(M(i,k)+L(k)<L(i))L(i)=L(k)+M(i,k);direction(i)=k;endendendsymbol(k)=1;sum=0;for i=1:mif(symbol(i)==1)sum=sum+1;endendif(sum==m)judge=0;endendp=first;i=2;arrow=zeros(1,m);arrow(1)=first;while p~=lastarrow(i)=direction(p);i=i+1;p=direction(p);endd=[0 7 5 12 inf infinf 0 inf 3 inf infinf inf 0 6 inf 1512 inf 6 0 inf 86 inf 13 inf 0 infinf 4 15 inf 9 0];[m,n]=size(d);p=zeros(m,n);for i=1:np(:,i)=i;endfor k=1:nfor i=1:mfor j=1:nif(d(i,k)+d(k,j)<d(i,j))d(i,j)=d(i,k)+d(k,j);p(i,j)=p(i,k);endendendend4.仿floyd 算法d=[inf 6 0 4 0 0 00 inf 0 0 5 0 04 7 inf 0 05 00 0 4 inf 0 3 00 0 2 0 inf 0 00 0 0 0 4 inf 50 0 0 0 6 0 inf];[m,n]=size(d);first=1;last=7;direction=zeros(m,m);for i=1:mdirection(:,i)=i;endfor i=1:mfor j=1:mfor k=1:msmall=min(d(i,k),d(k,j));if d(i,j)<smalld(i,j)=small;direction(i,j)=direction(i,k);endendendendarrow=zeros(1,m);arrow(1)=first;i=2;p=first;while p~=lastp=direction(p,last);arrow(i)=p;i=i+1;end—dijkstra算法d=[0 inf 3 5 inf10 0 14 inf 8inf inf 0 7 -6inf inf inf 0 infinf inf inf -1 0];[m,n]=size(d);first=2;last=4;L=zeros(1,n);z=zeros(m,n);symbol=zeros(1,n);direction=zeros(1,n);for i=1:nfor j=1:mif d(i,j)~=0if d(i,j)~=infz(i,j)=1;endendenddirection(i)=first;if i~=firstL(i)=inf;endendjudge=1;while judgemini=10;for j=1:nif symbol(j)==0sum=0;for i=1:mp=z(i,j)*(1-symbol(i));sum=sum+p;endif(sum==0)mini=j;breakendendendfor j=1:nif symbol(j)==0&&z(mini,j)==1if L(mini)+d(mini,j)<L(j)L(j)=L(mini)+d(mini,j);direction(j)=mini;endendendsymbol(mini)=1;num=0;for i=1:nif symbol(i)==1num=num+1;endendif num==m;judge=0;endendarrow=zeros(1,m);p=last;arrow(1)=last;i=2;while p~=firstp=direction(p);arrow(i)=p;i=i+1;end—dijkstra算法d=[0 inf 3 5 inf10 0 14 inf 8inf inf 0 7 -6inf inf inf 0 infinf inf inf -1 0];[m,n]=size(d);first=2;last=4;L=zeros(1,n);z=zeros(m,n);symbol=zeros(1,n);direction=zeros(1,n);for i=1:nfor j=1:mif d(i,j)~=0if d(i,j)~=infz(i,j)=1;endendenddirection(i)=last;if i~=lastL(i)=inf;endendjudge=1;while judgemini=10;for i=1:nif symbol(i)==0sum=0;for j=1:mp=z(i,j)*(1-symbol(j));sum=sum+p;endif(sum==0)mini=i;breakendendendfor i=1:nif symbol(i)==0&&z(i,mini)==1if L(mini)+d(i,mini)<L(i)L(i)=L(mini)+d(i,mini);direction(i)=mini;endendendsymbol(mini)=1;num=0;for i=1:nif symbol(i)==1num=num+1;endendif num==m;judge=0;endendarrow=zeros(1,m);p=first;arrow(1)=first;i=2;while p~=lastp=direction(p);arrow(i)=p;i=i+1;endM=[ 0 17 11 inf inf inf17 0 13 12 28 1511 13 0 inf 19 infinf 12 inf 0 inf 16inf 28 19 inf 0 10inf 15 inf 16 10 0];[m,n]=size(M);X=zeros(m,n);Y=zeros(m);Z=zeros(m);Y(1)=1;for i=2:mZ(i)=i;endjudge=1;while judgefor i=1:mif(Y(i)~=0)for j=1:mif(Z(j)~=0)min=M(i,j);a=i;b=j;endendendendfor i=1:mif(Y(i)~=0)for j=1:mif(Z(j)~=0)if(M(i,j)<min)min=M(i,j);a=i;b=j;endendendendendY(b)=b;Z(b)=0;X(a,b)=1;X(b,a)=1;c=0;for i=1:mif(Y(i)~=0)c=c+1;endendif(c==m)judge=0;endend网络最大流Ford—Fulkersen算法d=[inf 12 17 0 0 00 inf 0 8 0 00 6 inf 0 12 00 0 5 inf 0 150 0 0 4 inf 90 0 0 0 0 inf];[m,n]=size(d);X=zeros(m,n);first=1;last=6;recognize=1;while recognizeL=zeros(1,m);L(first)=inf;direction=ones(1,m);symbol=zeros(1,m);judge=1;while judgefor i=1:mif symbol(i)==0big=L(i);k=i;break;endendfor i=1:mif symbol(i)==0if L(i)>bigbig=L(i);k=i;endendendif k==nif L(n)==0breakendelsefor j=1:mif d(k,j)>0u=min(L(k),d(k,j)-X(k,j));if u>L(j)L(j)=u;direction(j)=k;endelseif d(j,k)>0u=min(L(k),X(j,k));if u>L(j)L(j)=u;direction(j)=k;endendendendendsymbol(k)=1;num=0;for i=1:mif symbol(i)==1num=num+1;endendif num==mjudge=0;endendafter=last;before=after;while before~=firstbefore=direction(after);if d(before,after)>0X(before,after)=X(before,after)+L(n); elseX(before,after)=X(before,after)-L(n); endafter=before;endif L(m)==0recognize=0;end end。

图算法的应用以及在Matlab中的实现图算法的应用以及在Matlab中的实现我们首先引入一个迷宫的路径求解问题。

我们用这样一个规模为N×M布尔类型的二维矩阵gaze[N][M]来描述迷宫：矩阵的每一个元素为平面上一小块方形区域，元素值为0代表该点不可通过，1代表可以通过。

下面给出一个迷宫的例子：令矩阵的规模为11×11。

maze[N][M]为：0 0 0 0 0 0 0 0 0 0 01 1 0 0 1 1 1 1 1 0 00 1 1 0 1 0 0 0 1 1 00 0 1 1 1 1 1 1 0 1 00 0 1 0 0 0 0 1 0 1 00 0 1 1 1 1 0 1 0 1 00 0 0 0 0 0 0 1 0 1 00 1 1 1 1 0 0 1 1 1 00 0 0 0 1 1 1 1 0 1 00 0 0 0 0 0 1 1 0 1 10 0 0 0 0 0 0 0 0 0 0其中入口为maze[2][1]，出口在maze[10][11]。

定义这个路径求解问题如下：找到一条从入口到出口的路径，只允许在值为1的区域上通过，而且允许走的过程中只有上下左右四个方向可以选择。

我们可以用一种很简单的方法找到一条路径：从入口处开始走，一直走到第一个分岔口A，假设有3条支路，分别编号为1、2、3，我们选择支路1，继续走，如果走不通，则返回A，走支路2。

如果遇到下一个分岔口按照同样的策略，直至走到出口处。

这样一个解的结构可以抽象成如下一棵树的结构。

由于入口和分岔口A之间仅有一条确定的路，可用A代替入口作为起始点。

O为出口。

由于路径可能不止一条，故O可能不止1个。

在对这样一个结构作深入分析之前，我们对树的结构进行定义。

首先命名该树为T。

我们定义上面一棵树上的每个点为结点，任意2结点之间的连线成为一条边，起点A是树T的根结点，取任意一条边（X，Y），称X是Y的父亲，Y是X的儿子，比如上图中，B是E 的父亲，E是B的儿子。

图论实验三个案例单源最短路径问题 1.1 Dijkstra 算法Dijkstra 算法是解单源最短路径问题的一个贪心算法。

其基本思想是，设置 一个顶点集合S 并不断地作贪心选择来扩充这个集合。

一个顶点属于集合S 当且 仅当从源到该顶点的最短路径长度已知。

设 v 是图中的一个顶点，记l(v)为顶点 v 到源点V 1的最短距离，V i,V jV ，若(V i,V j)E ，记“到百的权w 。

Dijkstra 算法：① S {V J I(V J 0 ； V V {可 1(V ) i i S V {V J ；J7JJJ7②S，停止，否则转③；l(v) min{ l(v) , d(V j ,v)}V j S④ 存在Vi 1，使l (V i l) min{l(V)}，V S ；⑤SSU{v i 1}S S {v i 1}i i 1实际上，Dijkstra 算法也是最优化原理的应用：如果V 1V 2LV n1Vn是从V1到Vn的最短路径，贝UV 1V 2L Vn1也必然是从V1到Vn 1的最优路径。

在下面的MATLA 实现代码中，我们用到了距离矩阵，矩阵第 i 行第j 行元 素表示顶点Vi到Vj的权Wj，若v 到V j无边，则W ijrealmax，其中realmax 是 MATLA 常量，表示最大的实数(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,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;%找到最小的顶点加入集合Send re=r;1.2动态规划求解最短路径动态规划是美国数学家 Richard Bellman 在1951年提出来的分析一类多阶 段决策过程的最优化方法，在工程技术、工业生产、经济管理、军事及现代化控 制工程等方面均有着广泛的应用。

图论算法matlab实现求最小费用最大流算法的 MATLAB 程序代码如下：n=5;C=[0 15 16 0 00 0 0 13 140 11 0 17 00 0 0 0 80 0 0 0 0]; %弧容量b=[0 4 1 0 00 0 0 6 10 2 0 3 00 0 0 0 20 0 0 0 0]; %弧上单位流量的费用wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流while(1)for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j);elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j);elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;endfor(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;end if(pd)break;end;end %求最短路的Ford 算法结束if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有向赋权图中不会含负权回路, 所以不会出现k=ndvt=Inf;t=n; %进入调整过程, dvt 表示调整量while(1) %计算调整量if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量if(dvt>dvtt)dvt=dvtt;endif(s(t)==1)break;end %当t 的标号为vs 时, 终止计算调整量t=s(t);end %继续调整前一段弧上的流fpd=0;if(wf+dvt>=wf0)dvt=wf0-wf;pd=1;end%如果最大流量大于或等于预定的流量值t=n;while(1) %调整过程if(a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt; %前向弧调整elseif(a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end %后向弧调整if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程t=s(t);endif(pd)break;end%如果最大流量达到预定的流量值wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%计算最小费用f %显示最小费用最大流图 6-22wf %显示最小费用最大流量zwf %显示最小费用, 程序结束__Kruskal 避圈法：Kruskal 避圈法的MATLAB 程序代码如下：n=8;A=[0 2 8 1 0 0 0 02 0 6 0 1 0 0 08 6 0 7 5 1 2 01 0 7 0 0 0 9 00 1 5 0 0 3 0 80 0 1 0 3 0 4 60 0 2 9 0 4 0 30 0 0 0 8 6 3 0];k=1; %记录A中不同正数的个数for(i=1:n-1)for(j=i+1:n) %此循环是查找A中所有不同的正数if(A(i,j)>0)x(k)=A(i,j); %数组x 记录A中不同的正数kk=1; %临时变量for(s=1:k-1)if(x(k)==x(s))kk=0;break;end;end %排除相同的正数k=k+kk;end;end;endk=k-1 %显示A中所有不同正数的个数for(i=1:k-1)for(j=i+1:k) %将x 中不同的正数从小到大排序if(x(j)<x(i))xx=x(j);x(j)=x(i);x(i)=xx;end;end;endT(n,n)=0; %将矩阵T 中所有的元素赋值为0q=0; %记录加入到树T 中的边数for(s=1:k)if(q==n)break;end %获得最小生成树T, 算法终止for(i=1:n-1)for(j=i+1:n)if (A(i,j)==x(s))T(i,j)=x(s);T(j,i)=x(s); %加入边到树T 中TT=T; %临时记录Twhile(1)pd=1; %砍掉TT 中所有的树枝for(y=1:n)kk=0;for(z=1:n)if(TT(y,z)>0)kk=kk+1;zz=z;end;end %寻找TT 中的树枝if(kk==1)TT(y,zz)=0;TT(zz,y)=0;pd=0;end;end %砍掉TT 中的树枝if(pd)break;end;end %已砍掉了TT 中所有的树枝pd=0; %判断TT 中是否有圈for(y=1:n-1)for(z=y+1:n)if(TT(y,z)>0)pd=1;break;end;end;endif(pd)T(i,j)=0;T(j,i)=0; %假如TT 中有圈else q=q+1;end;end;end;end;endT %显示近似最小生成树T, 程序结束用Warshall-Floyd 算法求任意两点间的最短路.n=8;A=[0 2 8 1 Inf Inf Inf Inf2 0 6 Inf 1 Inf Inf Inf8 6 0 7 5 1 2 Inf1 Inf 7 0 Inf Inf 9 InfInf 1 5 Inf 0 3 Inf 8Inf Inf 1 Inf 3 0 4 6Inf Inf 2 9 Inf 4 0 3Inf Inf Inf Inf 8 6 3 0]; % MATLAB 中, Inf 表示∞D=A; %赋初值for(i=1:n)for(j=1:n)R(i,j)=j;end;end %赋路径初值for(k=1:n)for(i=1:n)for(j=1:n)if(D(i,k)+D(k,j)<D(i,j))D(i,j)=D(i,k)+D(k,j); %更新dijR(i,j)=k;end;end;end %更新rijk %显示迭代步数D %显示每步迭代后的路长R %显示每步迭代后的路径pd=0;for i=1:n %含有负权时if(D(i,i)<0)pd=1;break;end;end %存在一条含有顶点vi 的负回路if(pd)break;end %存在一条负回路, 终止程序end %程序结束利用 Ford--Fulkerson 标号法求最大流算法的MATLAB 程序代码如下：n=8;C=[0 5 4 3 0 0 0 00 0 0 0 5 3 0 00 0 0 0 0 3 2 00 0 0 0 0 0 2 00 0 0 0 0 0 0 40 0 0 0 0 0 0 30 0 0 0 0 0 0 50 0 0 0 0 0 0 0]; %弧容量for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流for(i=1:n)No(i)=0;d(i)=0;end %No,d 记录标号图 6-19while(1)No(1)=n+1;d(1)=Inf; %给发点vs 标号while(1)pd=1; %标号过程for(i=1:n)if(No(i)) %选择一个已标号的点vifor(j=1:n)if(No(j)==0&f(i,j)<C(i,j)) %对于未给标号的点vj, 当vivj 为非饱和弧时No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;if(d(j)>d(i))d(j)=d(i);endelseif(No(j)==0&f(j,i)>0) %对于未给标号的点vj, 当vjvi 为非零流弧时No(j)=-i;d(j)=f(j,i);pd=0;if(d(j)>d(i))d(j)=d(i);end;end;end;end;endif(No(n)|pd)break;end;end%若收点vt 得到标号或者无法标号, 终止标号过程if(pd)break;end %vt 未得到标号, f 已是最大流, 算法终止dvt=d(n);t=n; %进入调整过程, dvt 表示调整量while(1)if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt; %前向弧调整elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvt;end %后向弧调整if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0; end;break;end %当t 的标号为vs 时, 终止调整过程t=No(t);end;end; %继续调整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);end %计算最大流量f %显示最大流wf %显示最大流量No %显示标号, 由此可得最小割, 程序结束图论程序大全程序一：关联矩阵和邻接矩阵互换算法function W=incandadf(F,f)if f==0m=sum(sum(F))/2;n=size(F,1);W=zeros(n,m);k=1;for i=1:nfor j=i:nif F(i,j)~=0W(i,k)=1;W(j,k)=1;k=k+1;endendendelseif f==1m=size(F,2);n=size(F,1);W=zeros(n,n);for i=1:ma=find(F(:,i)~=0);W(a(1),a(2))=1;W(a(2),a(1))=1;elsefprint('Please imput the right value of f');endW;程序二：可达矩阵算法function P=dgraf(A)n=size(A,1);P=A;for i=2:nP=P+A^i;endP(P~=0)=1;P;程序三：有向图关联矩阵和邻接矩阵互换算法function W=mattransf(F,f)if f==0m=sum(sum(F));n=size(F,1);W=zeros(n,m);k=1;for i=1:nfor j=i:nif F(i,j)~=0W(i,k)=1;W(j,k)=-1;k=k+1;endendendelseif f==1m=size(F,2);n=size(F,1);W=zeros(n,n);for i=1:ma=find(F(:,i)~=0);if F(a(1),i)==1W(a(1),a(2))=1;elseW(a(2),a(1))=1;endendfprint('Please imput the right value of f');endW;第二讲：最短路问题程序一：Dijkstra算法（计算两点间的最短路）function [l,z]=Dijkstra(W)n = size (W,1);for i = 1 :nl(i)=W(1,i);z(i)=0;endi=1;while i<=nfor j =1 :nif l(i)>l(j)+W(j,i)l(i)=l(j)+W(j,i);z(i)=j-1;if j<ii=j-1;endendendi=i+1;end程序二：floyd算法（计算任意两点间的最短距离）function [d,r]=floyd(a)n=size(a,1);d=a;for i=1:nfor j=1:nr(i,j)=j;endendr;for k=1:nfor i=1:nfor j=1:nif d(i,k)+d(k,j)<d(i,j)d(i,j)=d(i,k)+d(k,j);r(i,j)=r(i,k);endendendend程序三：n2short.m 计算指定两点间的最短距离function [P u]=n2short(W,k1,k2)n=length(W);U=W;m=1;while m<=nfor i=1:nfor j=1:nif U(i,j)>U(i,m)+U(m,j)U(i,j)=U(i,m)+U(m,j);endendendm=m+1;endu=U(k1,k2);P1=zeros(1,n);k=1;P1(k)=k2;V=ones(1,n)*inf;kk=k2;while kk~=k1for i=1:nV(1,i)=U(k1,kk)-W(i,kk);if V(1,i)==U(k1,i)P1(k+1)=i;kk=i;k=k+1;endendendk=1;wrow=find(P1~=0);for j=length(wrow):-1:1P(k)=P1(wrow(j));k=k+1;endP;程序四、n1short.m(计算某点到其它所有点的最短距离)function[Pm D]=n1short(W,k)n=size(W,1);D=zeros(1,n);for i=1:n[P d]=n2short(W,k,i);Pm{i}=P;D(i)=d;end程序五：pass2short.m(计算经过某两点的最短距离)function [P d]=pass2short(W,k1,k2,t1,t2)[p1 d1]=n2short(W,k1,t1);[p2 d2]=n2short(W,t1,t2);[p3 d3]=n2short(W,t2,k2);dt1=d1+d2+d3;[p4 d4]=n2short(W,k1,t2);[p5 d5]=n2short(W,t2,t1);[p6 d6]=n2short(W,t1,k2);dt2=d4+d5+d6;if dt1<dt2d=dt1;P=[p1 p2(2:length(p2)) p3(2:length(p3))];elsed=dt1;p=[p4 p5(2:length(p5)) p6(2:length(p6))];endP;d;第三讲：最小生成树程序一：最小生成树的Kruskal算法function [T c]=krusf(d,flag)if nargin==1n=size(d,2);m=sum(sum(d~=0))/2;b=zeros(3,m);k=1;for i=1:nfor j=(i+1):nif d(i,j)~=0b(1,k)=i;b(2,k)=j;b(3,k)=d(i,j);k=k+1;endendendelseb=d;endn=max(max(b(1:2,:)));m=size(b,2);[B,i]=sortrows(b',3);B=B';c=0;T=[];k=1;t=1:n;for i=1:mif t(B(1,i))~=t(B(2,i))T(1:2,k)=B(1:2,i);c=c+B(3,i);k=k+1;tmin=min(t(B(1,i)),t(B(2,i)));tmax=max(t(B(1,i)),t(B(2,i)));for j=1:nif t(j)==tmaxt(j)=tmin;endendendif k==nbreak;endendT;c;程序二：最小生成树的Prim算法function [T c]=Primf(a)l=length(a);a(a==0)=inf;k=1:l;listV(k)=0;listV(1)=1;e=1;while (e<l)min=inf;for i=1:lif listV(i)==1for j=1:lif listV(j)==0 & min>a(i,j)min=a(i,j);b=a(i,j);s=i;d=j;endendendendlistV(d)=1;distance(e)=b;source(e)=s;destination(e)=d;e=e+1;endT=[source;destination];for g=1:e-1c(g)=a(T(1,g),T(2,g));endc;另外两种程序最小生成树程序1（prim 算法构造最小生成树）a=[inf 50 60 inf inf inf inf;50 inf inf 65 40 inf inf;60 inf inf 52 inf inf 45;...inf 65 52 inf 50 30 42;inf 40 inf 50 inf 70 inf;inf inf inf 30 70 inf inf;...inf inf 45 42 inf inf inf];result=[];p=1;tb=2:length(a);while length(result)~=length(a)-1temp=a(p,tb);temp=temp(:);d=min(temp);[jb,kb]=find(a(p,tb)==d);j=p(jb(1));k=tb(kb(1));result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];endresult最小生成树程序2（Kruskal 算法构造最小生成树）clc;clear;a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70;[i,j,b]=find(a);data=[i';j';b'];index=data(1:2,:);loop=max(size(a))-1;result=[];while length(result)<looptemp=min(data(3,:));flag=find(data(3,:)==temp);flag=flag(1);v1=data(1,flag);v2=data(2,flag);if index(1,flag)~=index(2,flag)result=[result,data(:,flag)];endindex(find(index==v2))=v1;data(:,flag)=[];index(:,flag)=[];endresult第四讲：Euler图和Hamilton图程序一：Fleury算法（在一个Euler图中找出Euler环游）注：包括三个文件；fleuf1.m, edf.m, flecvexf.mfunction [T c]=fleuf1(d)%注：必须保证是Euler环游，否则输出T=0,c=0n=length(d);b=d;b(b==inf)=0;b(b~=0)=1;m=0;a=sum(b);eds=sum(a)/2;ed=zeros(2,eds);vexs=zeros(1,eds+1);matr=b;for i=1:nif mod(a(i),2)==1m=m+1;endendif m~=0fprintf('there is not exit Euler path.\n')T=0;c=0;endif m==0vet=1;flag=0;t1=find(matr(vet,:)==1);for ii=1:length(t1)ed(:,1)=[vet,t1(ii)];vexs(1,1)=vet;vexs(1,2)=t1(ii);matr(vexs(1,2),vexs(1,1))=0;flagg=1;tem=1;while flagg[flagg ed]=edf(matr,eds,vexs,ed,tem); tem=tem+1;if ed(1,eds)~=0 & ed(2,eds)~=0T=ed;T(2,eds)=1;c=0;for g=1:edsc=c+d(T(1,g),T(2,g));endflagg=0;break;endendendendfunction[flag ed]=edf(matr,eds,vexs,ed,tem)flag=1;for i=2:eds[dvex f]=flecvexf(matr,i,vexs,eds,ed,tem);if f==1flag=0;break;endif dvex~=0ed(:,i)=[vexs(1,i) dvex];vexs(1,i+1)=dvex;matr(vexs(1,i+1),vexs(1,i))=0;elsebreak;endfunction [dvex f]=flecvexf(matr,i,vexs,eds,ed,temp) f=0;edd=find(matr(vexs(1,i),:)==1);dvex=0;dvex1=[];ded=[];if length(edd)==1dvex=edd;elsedd=1;dd1=0;kkk=0;for kk=1:length(edd)m1=find(vexs==edd(kk));if sum(m1)==0dvex1(dd)=edd(kk);dd=dd+1;dd1=1;elsekkk=kkk+1;endendif kkk==length(edd)tem=vexs(1,i)*ones(1,kkk);edd1=[tem;edd];for l1=1:kkklt=0;ddd=1;for l2=1:edsif edd1(1:2,l1)==ed(1:2,l2)lt=lt+1;endendif lt==0ded(ddd)=edd(l1);ddd=ddd+1;endendendif temp<=length(dvex1)dvex=dvex1(temp);elseif temp>length(dvex1) & temp<=length(ded) dvex=ded(temp);elsef=1;end程序二：Hamilton改良圈算法（找出比较好的Hamilton路）function [C d1]= hamiltonglf(v)%d表示权值矩阵%C表示算法最终找到的Hamilton圈。

图论算法matlab实现求最小费用最大流算法的 MATLAB 程序代码如下：n=5;C=[0 15 16 0 00 0 0 13 140 11 0 17 00 0 0 0 80 0 0 0 0]; %弧容量b=[0 4 1 0 00 0 0 6 10 2 0 3 00 0 0 0 20 0 0 0 0]; %弧上单位流量的费用wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流while(1)for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j);elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s( i)=j;pd=0;end;end;endif(pd)break;end;end %求最短路的Ford 算法结束if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有向赋权图中不会含负权回路, 所以不会出现k=ndvt=Inf;t=n; %进入调整过程, dvt 表示调整量while(1) %计算调整量if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量if(dvt>dvtt)dvt=dvtt;endif(s(t)==1)break;end %当t 的标号为vs 时, 终止计算调整量t=s(t);end %继续调整前一段弧上的流fpd=0;if(wf+dvt>=wf0)dvt=wf0-wf;pd=1;end%如果最大流量大于或等于预定的流量值t=n;while(1) %调整过程if(a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt; %前向弧调整elseif(a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end %后向弧调整if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程t=s(t);endif(pd)break;end%如果最大流量达到预定的流量值wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%计算最小费用f %显示最小费用最大流图 6-22wf %显示最小费用最大流量zwf %显示最小费用, 程序结束__Kruskal 避圈法：Kruskal 避圈法的MATLAB 程序代码如下：n=8;A=[0 2 8 1 0 0 0 02 0 6 0 1 0 0 08 6 0 7 5 1 2 01 0 7 0 0 0 9 00 1 5 0 0 3 0 80 0 1 0 3 0 4 60 0 2 9 0 4 0 30 0 0 0 8 6 3 0];k=1; %记录A中不同正数的个数for(i=1:n-1)for(j=i+1:n) %此循环是查找A中所有不同的正数if(A(i,j)>0)x(k)=A(i,j); %数组x 记录A中不同的正数kk=1; %临时变量for(s=1:k-1)if(x(k)==x(s))kk=0;break;end;end %排除相同的正数k=k+kk;end;end;endk=k-1 %显示A中所有不同正数的个数for(i=1:k-1)for(j=i+1:k) %将x 中不同的正数从小到大排序if(x(j)<x(i))xx=x(j);x(j)=x(i);x(i)=xx;end;end;endT(n,n)=0; %将矩阵T 中所有的元素赋值为0q=0; %记录加入到树T 中的边数for(s=1:k)if(q==n)break;end %获得最小生成树T, 算法终止for(i=1:n-1)for(j=i+1:n)if(A(i,j)==x(s))T(i,j)=x(s);T(j,i)=x(s); %加入边到树T 中TT=T; %临时记录Twhile(1)pd=1; %砍掉TT 中所有的树枝for(y=1:n)kk=0;for(z=1:n)if(TT(y,z)>0)kk=kk+1;zz=z;end;end %寻找TT 中的树枝if(kk==1)TT(y,zz)=0;TT(zz,y)=0;pd=0;end;end %砍掉TT 中的树枝if(pd)break;end;end %已砍掉了TT 中所有的树枝pd=0; %判断TT 中是否有圈for(y=1:n-1)for(z=y+1:n)if(TT(y,z)>0)pd=1;break;end;end;end if(pd)T(i,j)=0;T(j,i)=0; %假如TT 中有圈else q=q+1;end;end;end;end;endT %显示近似最小生成树T, 程序结束用Warshall-Floyd 算法求任意两点间的最短路.n=8;A=[0 2 8 1 Inf Inf Inf Inf2 0 6 Inf 1 Inf Inf Inf8 6 0 7 5 1 2 Inf1 Inf 7 0 Inf Inf 9 Inf Inf 1 5 Inf 0 3 Inf 8 Inf Inf 1 Inf 3 0 4 6Inf Inf 2 9 Inf 4 0 3Inf Inf Inf Inf 8 6 3 0]; % MATLAB 中, Inf 表示∞D=A; %赋初值for(i=1:n)for(j=1:n)R(i,j)=j;end;end %赋路径初值for(k=1:n)for(i=1:n)for(j=1:n)if(D(i,k)+D(k,j)<D(i,j))D(i,j )=D(i,k)+D(k,j); %更新dijR(i,j)=k;end;end;end %更新rijk %显示迭代步数D %显示每步迭代后的路长R %显示每步迭代后的路径pd=0;for i=1:n %含有负权时if(D(i,i)<0)pd=1;break;end;end %存在一条含有顶点vi 的负回路if(pd)break;end %存在一条负回路, 终止程序end %程序结束利用 Ford--Fulkerson 标号法求最大流算法的MATLAB 程序代码如下：n=8;C=[0 5 4 3 0 0 0 00 0 0 0 5 3 0 00 0 0 0 0 3 2 00 0 0 0 0 0 2 00 0 0 0 0 0 0 40 0 0 0 0 0 0 30 0 0 0 0 0 0 50 0 0 0 0 0 0 0]; %弧容量for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流for(i=1:n)No(i)=0;d(i)=0;end %No,d 记录标号图 6-19while(1)No(1)=n+1;d(1)=Inf; %给发点vs 标号while(1)pd=1; %标号过程for(i=1:n)if(No(i)) %选择一个已标号的点vifor(j=1:n)if(No(j)==0&f(i,j)<C(i,j)) %对于未给标号的点vj, 当vivj 为非饱和弧时No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;if(d(j)>d(i))d(j)=d(i);endelseif(No(j)==0&f(j,i)>0) %对于未给标号的点vj, 当vjvi 为非零流弧时No(j)=-i;d(j)=f(j,i);pd=0;if(d(j)>d(i))d(j)=d(i);end;end;end;end;endif(No(n)|pd)break;end;end%若收点vt 得到标号或者无法标号, 终止标号过程if(pd)break;end %vt 未得到标号, f 已是最大流, 算法终止dvt=d(n);t=n; %进入调整过程, dvt 表示调整量while(1)if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt; %前向弧调整elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvt;end %后向弧调整if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0; end;break;end %当t 的标号为vs 时, 终止调整过程t=No(t);end;end; %继续调整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);end %计算最大流量f %显示最大流wf %显示最大流量No %显示标号, 由此可得最小割, 程序结束图论程序大全程序一：关联矩阵和邻接矩阵互换算法function W=incandadf(F,f)if f==0m=sum(sum(F))/2;n=size(F,1);W=zeros(n,m);k=1;for i=1:nfor j=i:nif F(i,j)~=0W(i,k)=1;W(j,k)=1;k=k+1;endendendelseif f==1m=size(F,2);n=size(F,1);W=zeros(n,n);for i=1:ma=find(F(:,i)~=0);W(a(1),a(2))=1;W(a(2),a(1))=1;endelsefprint('Please imput the right value of f');endW;程序二：可达矩阵算法function P=dgraf(A) n=size(A,1);P=A;for i=2:nP=P+A^i;endP(P~=0)=1;P;程序三：有向图关联矩阵和邻接矩阵互换算法function W=mattransf(F,f)if f==0m=sum(sum(F));n=size(F,1);W=zeros(n,m);k=1;for i=1:nfor j=i:nif F(i,j)~=0W(i,k)=1;W(j,k)=-1;k=k+1;endendendelseif f==1m=size(F,2);n=size(F,1);W=zeros(n,n);for i=1:ma=find(F(:,i)~=0);if F(a(1),i)==1W(a(1),a(2))=1;elseW(a(2),a(1))=1;endendelsefprint('Please imput the right value of f');endW;第二讲：最短路问题程序一：Dijkstra算法（计算两点间的最短路）function [l,z]=Dijkstra(W)n = size (W,1); for i = 1 :nl(i)=W(1,i);z(i)=0;endi=1;while i<=nfor j =1 :nif l(i)>l(j)+W(j,i)l(i)=l(j)+W(j,i);z(i)=j-1;if j<ii=j-1;endendendi=i+1;end程序二：floyd算法（计算任意两点间的最短距离）function [d,r]=floyd(a)n=size(a,1);d=a;for i=1:nfor j=1:nr(i,j)=j;endendr;for k=1:nfor i=1:nfor j=1:nif d(i,k)+d(k,j)<d(i,j)d(i,j)=d(i,k)+d(k,j);r(i,j)=r(i,k);endendendend程序三：n2short.m 计算指定两点间的最短距离function [P u]=n2short(W,k1,k2)n=length(W);U=W;m=1;while m<=nfor i=1:nfor j=1:nif U(i,j)>U(i,m)+U(m,j)U(i,j)=U(i,m)+U(m,j);endendendm=m+1;endu=U(k1,k2);P1=zeros(1,n);k=1;P1(k)=k2;V=ones(1,n)*inf;kk=k2;while kk~=k1for i=1:nV(1,i)=U(k1,kk)-W(i,kk);if V(1,i)==U(k1,i)P1(k+1)=i;kk=i;k=k+1;endendendk=1;wrow=find(P1~=0);for j=length(wrow):-1:1P(k)=P1(wrow(j));k=k+1;endP;程序四、n1short.m(计算某点到其它所有点的最短距离)function[Pm D]=n1short(W,k)n=size(W,1);D=zeros(1,n);for i=1:n[P d]=n2short(W,k,i);Pm{i}=P;D(i)=d;end程序五：pass2short.m(计算经过某两点的最短距离)function [P d]=pass2short(W,k1,k2,t1,t2)[p1 d1]=n2short(W,k1,t1);[p2 d2]=n2short(W,t1,t2);[p3 d3]=n2short(W,t2,k2);dt1=d1+d2+d3;[p4 d4]=n2short(W,k1,t2);[p5 d5]=n2short(W,t2,t1);[p6 d6]=n2short(W,t1,k2);dt2=d4+d5+d6;if dt1<dt2d=dt1;P=[p1 p2(2:length(p2)) p3(2:length(p3))];elsed=dt1;p=[p4 p5(2:length(p5)) p6(2:length(p6))];endP;d;第三讲：最小生成树程序一：最小生成树的Kruskal算法function [T c]=krusf(d,flag)if nargin==1n=size(d,2);m=sum(sum(d~=0))/2;b=zeros(3,m);k=1;for i=1:nfor j=(i+1):nif d(i,j)~=0b(1,k)=i;b(2,k)=j;b(3,k)=d(i,j);k=k+1;endendendelseb=d;endn=max(max(b(1:2,:)));m=size(b,2);[B,i]=sortrows(b',3);B=B';c=0;T=[];k=1;t=1:n;for i=1:mif t(B(1,i))~=t(B(2,i))T(1:2,k)=B(1:2,i);c=c+B(3,i);k=k+1;tmin=min(t(B(1,i)),t(B(2,i)));tmax=max(t(B(1,i)),t(B(2,i)));for j=1:nif t(j)==tmaxt(j)=tmin;endendendif k==nbreak;endendT;c;程序二：最小生成树的Prim算法function [T c]=Primf(a)l=length(a);a(a==0)=inf;k=1:l;listV(k)=0;listV(1)=1;e=1;while (e<l)min=inf;for i=1:lif listV(i)==1for j=1:lif listV(j)==0 & min>a(i,j)min=a(i,j);b=a(i,j);s=i;d=j;endendendendlistV(d)=1;distance(e)=b;source(e)=s;destination(e)=d;e=e+1;endT=[source;destination]; for g=1:e-1c(g)=a(T(1,g),T(2,g));endc;另外两种程序最小生成树程序1（prim 算法构造最小生成树）a=[inf 50 60 inf inf inf inf;50 inf inf 65 40 inf inf;60 inf inf 52 inf inf 45;...inf 65 52 inf 50 30 42;inf 40 inf 50 inf 70 inf;inf inf inf 30 70 inf inf;...inf inf 45 42 inf inf inf];result=[];p=1;tb=2:length(a);while length(result)~=length(a)-1temp=a(p,tb);temp=temp(:);d=min(temp);[jb,kb]=find(a(p,tb)==d);j=p(jb(1));k=tb(kb(1));result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];endresult最小生成树程序2（Kruskal 算法构造最小生成树）clc;clear;a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70;[i,j,b]=find(a);data=[i';j';b'];index=data(1:2,:);loop=max(size(a))-1;result=[];while length(result)<looptemp=min(data(3,:));flag=find(data(3,:)==temp);flag=flag(1);v1=data(1,flag);v2=data(2,flag);if index(1,flag)~=index(2,flag)result=[result,data(:,flag)];endindex(find(index==v2))=v1;data(:,flag)=[];index(:,flag)=[];endresult第四讲：Euler图和Hamilton图程序一：Fleury算法（在一个Euler图中找出Euler环游）注：包括三个文件；fleuf1.m, edf.m, flecvexf.mfunction [T c]=fleuf1(d)%注：必须保证是Euler环游，否则输出T=0,c=0 n=length(d);b=d;b(b==inf)=0;b(b~=0)=1;m=0;a=sum(b);eds=sum(a)/2;ed=zeros(2,eds);vexs=zeros(1,eds+1);matr=b;for i=1:nif mod(a(i),2)==1m=m+1;endendif m~=0fprintf('there is not exit Euler path.\n')T=0;c=0;endif m==0vet=1;flag=0;t1=find(matr(vet,:)==1);for ii=1:length(t1)ed(:,1)=[vet,t1(ii)];vexs(1,1)=vet;vexs(1,2)=t1(ii);matr(vexs(1,2),vexs(1,1))=0;flagg=1;tem=1;while flagg[flagg ed]=edf(matr,eds,vexs,ed,tem); tem=tem+1;if ed(1,eds)~=0 & ed(2,eds)~=0T=ed;T(2,eds)=1;c=0;for g=1:edsc=c+d(T(1,g),T(2,g));endflagg=0;break;endendendendfunction[flag ed]=edf(matr,eds,vexs,ed,tem)flag=1;for i=2:eds[dvex f]=flecvexf(matr,i,vexs,eds,ed,tem);if f==1flag=0;break;endif dvex~=0ed(:,i)=[vexs(1,i) dvex];vexs(1,i+1)=dvex;matr(vexs(1,i+1),vexs(1,i))=0;elsebreak;endendfunction [dvex f]=flecvexf(matr,i,vexs,eds,ed,temp) f=0;edd=find(matr(vexs(1,i),:)==1);dvex=0;dvex1=[];ded=[];if length(edd)==1dvex=edd;elsedd=1;dd1=0;kkk=0;for kk=1:length(edd)m1=find(vexs==edd(kk));if sum(m1)==0dvex1(dd)=edd(kk);dd=dd+1;dd1=1;elsekkk=kkk+1;endendif kkk==length(edd)tem=vexs(1,i)*ones(1,kkk);edd1=[tem;edd];for l1=1:kkklt=0;ddd=1;for l2=1:edsif edd1(1:2,l1)==ed(1:2,l2)lt=lt+1;endendif lt==0ded(ddd)=edd(l1); ddd=ddd+1;endendendif temp<=length(dvex1)dvex=dvex1(temp);elseif temp>length(dvex1) & temp<=length(ded)dvex=ded(temp);elsef=1;endend程序二：Hamilton改良圈算法（找出比较好的Hamilton路）function [C d1]= hamiltonglf(v)%d表示权值矩阵%C表示算法最终找到的Hamilton圈。

人、狼、羊、菜安全渡河问题安全渡河问题又称作“人狼羊菜”问题，其具体描述为：一个人带着一条狼、一只羊、一筐白菜过河但由于船太小，人一次只能带一样东西乘船过河。

狼和羊、羊和白菜不能单独留在同岸，否则羊或白菜会被吃掉。

该问题可使用图论中的最短路算法进行求解。

问题分析根据题意，人不在场时，狼要吃羊，羊要吃菜，因此，人不在场时，不能将狼与羊、羊与菜留在河的任一岸。

可用四维向量v=（m，n，p，q）来表示状态，m表示人，n代表狼，p代表羊，q代表白菜，且m,n,p,q ∈{0,1},0代表在对岸，1代表在此岸。

例如，状态（0,1,1,0）表示人和菜在对岸，而狼和羊在此岸，这时人不在场，狼要吃羊，因此，这个状态是不可行的。

通过穷举法将所有可行的状态列举出来，可行的状态有（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）。

可行状态共有十种。

每一次的渡河行为改变现有的状态。

现构造赋权图G=(V,E,W),其中顶点集V={v1,…, v10}中的顶点（按照上面的顺序编号）分别表示上述１０个可行状态，当且仅当对应的两个可行状态之间存在一个可行转移时两顶点之间才有边连接，并且对应的权重取为１，当两个顶点之间不存在可行转移时，可以把相应的权重取为∞。

因此问题变为在图Ｇ中寻找一条由初始状态（１,１,１,１）出发，经最小次数转移到达最终状态（０,０,０,０）的转移过程，即求从状态（１,１,１,１）到状态（０,０,０,０）的最短路径。

该问题难点在于计算邻接矩阵，由于摆渡一次就改变现有状态，为此再引入一个四维状态转移向量，用它来反映摆渡情况。

用１表示过河，０表示未过河。

例如，（１,１,０,０）表示人带狼过河。

状态转移只有四种情况，用如下向量表示：（１,０,０,０），（１,１,０,０），（１,０,１,０），（１,０,０,１）现在规定状态向量与转移向量之间的运算为0+0=0,1+0=1,0+1=1,1+1=0通过上面的定义，如果某一个可行状态加上转移向量得到的新向量还属于可行状态，则这两个可行状态对应的顶点之间就存在一条边。

图论算法及其MATLAB 程序代码求赋权图G = (V , E , F )中任意两点间的最短路的Warshall-Floyd 算法：设A = (a ij )n ×n 为赋权图G = (V , E , F )的矩阵, 当v i v j ∈E 时a ij = F (v i v j ), 否则取a ii =0, a ij = +∞(i ≠j ), d ij 表示从v i 到v j 点的距离, r ij 表示从v i 到v j 点的最短路中一个点的编号.① 赋初值. 对所有i , j , d ij = a ij , r ij = j . k = 1. 转向②② 更新d ij , r ij . 对所有i , j , 若d ik + d k j ＜d ij , 则令d ij = d ik + d k j , r ij = k , 转向③.③ 终止判断. 若d ii ＜0, 则存在一条含有顶点v i 的负回路, 终止; 或者k = n 终止; 否则令k = k + 1, 转向②.最短路线可由r ij 得到.例1 求图6-4中任意两点间的最短路.解：用Warshall-Floyd 算法, MATLAB 程序代码如下：n=8;A=[0 2 8 1 Inf Inf Inf Inf2 0 6 Inf 1 Inf Inf Inf8 6 0 7 5 1 2 Inf1 Inf 7 0 Inf Inf 9 InfInf 1 5 Inf 0 3 Inf 8Inf Inf 1 Inf 3 0 4 6Inf Inf 2 9 Inf 4 0 3Inf Inf Inf Inf 8 6 3 0]; % MATLAB 中, Inf 表示∞D=A; %赋初值for (i=1:n)for (j=1:n)R(i,j)=j;end ;end %赋路径初值for (k=1:n)for (i=1:n)for (j=1:n)if (D(i,k)+D(k,j)<D(i,j))D(i,j)=D(i,k)+D(k,j); %更新dijR(i,j)=k;end ;end ;end %更新rijk %显示迭代步数D %显示每步迭代后的路长R %显示每步迭代后的路径pd=0;for i=1:n %含有负权时if (D(i,i)<0)pd=1;break ;end ;end %存在一条含有顶点vi 的负回路if (pd)break ;end %存在一条负回路, 终止程序end %程序结束图6-4Kruskal避圈法：将图G中的边按权数从小到大逐条考察, 按不构成圈的原则加入到T 中(若有选择时, 不同的选择可能会导致最后生成树的权数不同), 直到q (T ) = p (G ) − 1为止, 即T的边数= G的顶点数− 1为止.Kruskal避圈法的MATLAB程序代码如下：n=8;A=[0 2 8 1 0 0 0 02 0 6 0 1 0 0 08 6 0 7 5 1 2 01 0 7 0 0 0 9 00 1 5 0 0 3 0 80 0 1 0 3 0 4 60 0 2 9 0 4 0 30 0 0 0 8 6 3 0];k=1; %记录A中不同正数的个数for(i=1:n-1)for(j=i+1:n) %此循环是查找A中所有不同的正数if(A(i,j)>0)x(k)=A(i,j); %数组x记录A中不同的正数kk=1; %临时变量for(s=1:k-1)if(x(k)==x(s))kk=0;break;end;end%排除相同的正数k=k+kk;end;end;endk=k-1 %显示A中所有不同正数的个数for(i=1:k-1)for(j=i+1:k) %将x中不同的正数从小到大排序if(x(j)<x(i))xx=x(j);x(j)=x(i);x(i)=xx;end;end;endT(n,n)=0; %将矩阵T中所有的元素赋值为0q=0; %记录加入到树T中的边数for(s=1:k)if(q==n)break;end%获得最小生成树T, 算法终止for(i=1:n-1)for(j=i+1:n)if (A(i,j)==x(s))T(i,j)=x(s);T(j,i)=x(s); %加入边到树T中TT=T; %临时记录Twhile(1)pd=1;%砍掉TT中所有的树枝for(y=1:n)kk=0;for(z=1:n)if(TT(y,z)>0)kk=kk+1;zz=z;end;end%寻找TT中的树枝if(kk==1)TT(y,zz)=0;TT(zz,y)=0;pd=0;end;end%砍掉TT中的树枝if(pd)break;end;end%已砍掉了TT中所有的树枝pd=0;%判断TT中是否有圈for(y=1:n-1)for(z=y+1:n)if(TT(y,z)>0)pd=1;break;end;end;endif(pd)T(i,j)=0;T(j,i)=0;%假如TT中有圈else q=q+1;end;end;end;end;endT %显示近似最小生成树T, 程序结束求二部图G的最大匹配的算法(匈牙利算法), 其基本思想是：从G的任意匹配M开始, 对X中所有M的非饱和点, 寻找M−增广路. 若不存在M−增广路, 则M为最大匹配; 若存在M−增广路P, 则将P中M与非M的边互换得到比M多一边的匹配M1 , 再对M1重复上述过程.设G = ( X, Y, E )为二部图, 其中X = {x1, x2, … , x n }, Y = { y1, y2, … , y n}. 任取G的一初始匹配M (如任取e∈E, 则M = {e}是一个匹配).①令S = φ , T = φ , 转向②.②若M饱和X \S的所有点, 则M是二部图G的最大匹配. 否则, 任取M的非饱和点u∈X \ S , 令S = S ∪{ u }, 转向③.③记N (S ) = {v | u∈S, uv∈E}. 若N (S ) = T, 转向②. 否则取y∈N (S ) \T. 若y是M 的饱和点, 转向④, 否则转向⑤.④设x y∈M, 则令S = S ∪{ x }, T = T ∪{ y }, 转向③.⑤u −y路是M−增广路, 设为P, 并令M = M⊕P, 转向①. 这里M⊕P = M∪P \M∩P, 是对称差.由于计算M−增广路P比较麻烦, 因此将迭代步骤改为：①将X中M的所有非饱和点(不是M中某条边的端点)都给以标号0和标记*, 转向②.②若X中所有有标号的点都已去掉了标记*, 则M是G的最大匹配. 否则任取X中一个既有标号又有标记*的点x i , 去掉x i的标记*, 转向③.③找出在G中所有与x i邻接的点y j (即x i y j∈E ), 若所有这样的y j都已有标号, 则转向②, 否则转向④.④对与x i邻接且尚未给标号的y j都给定标号i. 若所有的y j都是M的饱和点, 则转向⑤, 否则逆向返回. 即由其中M的任一个非饱和点y j的标号i找到x i, 再由x i的标号k找到y k , … , 最后由y t的标号s找到标号为0的x s时结束, 获得M−增广路x s y t…x i y j, 记P = {x s y t, …, x i y j }, 重新记M为M⊕P, 转向①.⑤将y j在M中与之邻接的点x k (即x k y j∈M), 给以标号j和标记*, 转向②.例1求图6-9中所示的二部图G的最大匹配.图6-9匈牙利算法的MATLAB程序代码如下：m=5;n=5;A=[0 1 1 0 01 1 0 1 10 1 1 0 00 1 1 0 00 0 0 1 1];M(m,n)=0;for(i=1:m)for(j=1:n)if(A(i,j))M(i,j)=1;break;end;end%求初始匹配Mif(M(i,j))break;end;end%获得仅含一条边的初始匹配Mwhile(1)for(i=1:m)x(i)=0;end%将记录X中点的标号和标记*for(i=1:n)y(i)=0;end%将记录Y中点的标号和标记*for(i=1:m)pd=1;%寻找X中M的所有非饱和点for(j=1:n)if(M(i,j))pd=0;end;endif(pd)x(i)=-n-1;end;end%将X中M的所有非饱和点都给以标号0和标记*, 程序中用n+1表示0标号, 标号为负数时表示标记*pd=0;while(1)xi=0;for(i=1:m)if(x(i)<0)xi=i;break;end;end%假如X中存在一个既有标号又有标记*的点, 则任取X中一个既有标号又有标记*的点xiif(xi==0)pd=1;break;end%假如X中所有有标号的点都已去掉了标记*, 算法终止x(xi)=x(xi)*(-1); %去掉xi的标记*k=1;for(j=1:n)if(A(xi,j)&y(j)==0)y(j)=xi;yy(k)=j;k=k+1;end;end%对与xi邻接且尚未给标号的yj都给以标号iif(k>1)k=k-1;for(j=1:k)pdd=1;for(i=1:m)if(M(i,yy(j)))x(i)=-yy(j);pdd=0;break;end;end%将yj在M中与之邻接的点xk (即xkyj∈M), 给以标号j和标记*if(pdd)break;end;endif(pdd)k=1;j=yy(j); %yj不是M的饱和点while(1)P(k,2)=j;P(k,1)=y(j);j=abs(x(y(j))); %任取M的一个非饱和点yj, 逆向返回if(j==n+1)break;end%找到X中标号为0的点时结束, 获得M-增广路Pk=k+1;endfor(i=1:k)if(M(P(i,1),P(i,2)))M(P(i,1),P(i,2))=0; %将匹配M在增广路P中出现的边去掉else M(P(i,1),P(i,2))=1;end;end%将增广路P中没有在匹配M中出现的边加入到匹配M中break;end;end;endif(pd)break;end;end%假如X中所有有标号的点都已去掉了标记*, 算法终止M %显示最大匹配M, 程序结束利用可行点标记求最佳匹配的算法步骤如下：设G = ( X , Y , E , F )为完备的二部赋权图, L 是其一个初始可行点标记, 通常取.,,0)(},|)(max{)(Y y X x y L Y y xy F x L ∈∈ =∈= M 是G L 的一个匹配. ① 若X 的每个点都是M 的饱和点, 则M 是最佳匹配. 否则取M 的非饱和点u ∈X , 令S = {u }, T = φ , 转向②.② 记N L (S ) = {v | u ∈S , uv ∈E L }. 若N L ( S ) = T , 则G L 没有完美匹配, 转向③. 否则转向④.③ 调整可行点标记, 计算a L = min { L ( x ) + L ( y ) − F (x y ) | x ∈S , y ∈Y \T }.由此得新的可行顶点标记H (v ) =,,),(,)(,)(T v S v v L a v L a v L L L ∈∈+−令L = H , G L = G H , 重新给出G L 的一个匹配M , 转向①.④ 取y ∈N L ( S ) \T , 若y 是M 的饱和点, 转向⑤. 否则, 转向⑥.⑤ 设x y ∈M , 则令S = S ∪{ x }, T = T ∪{ y }, 转向②.⑥ 在G L 中的u − y 路是M −增广路, 记为P , 并令 M = M ⊕P , 转向①.利用可行点标记求最佳匹配算法的MATLAB 程序代码如下：n=4;A=[4 5 5 12 2 4 64 2 3 35 0 2 1];for (i=1:n)L(i,1)=0;L(i,2)=0;endfor (i=1:n)for (j=1:n)if (L(i,1)<A(i,j))L(i,1)=A(i,j);end ; %初始可行点标记LM(i,j)=0;end ;endfor (i=1:n)for (j=1:n) %生成子图Glif (L(i,1)+L(j,2)==A(i,j))Gl(i,j)=1;else Gl(i,j)=0;end ;end ;endii=0;jj=0;for (i=1:n)for (j=1:n)if (Gl(i,j))ii=i;jj=j;break ;end ;endif (ii)break ;end ;end %获得仅含Gl 的一条边的初始匹配MM(ii,jj)=1;for (i=1:n)S(i)=0;T(i)=0;NlS(i)=0;endwhile (1)for (i=1:n)k=1;否则.for(j=1:n)if(M(i,j))k=0;break;end;endif(k)break;end;endif(k==0)break;end%获得最佳匹配M, 算法终止S(1)=i;jss=1;jst=0;%S={xi}, T=φwhile(1)jsn=0;for(i=1:jss)for(j=1:n)if(Gl(S(i),j))jsn=jsn+1;NlS(jsn)=j;%NL(S)={v|u∈S,uv∈EL}for(k=1:jsn-1)if(NlS(k)==j)jsn=jsn-1;end;end;end;end;endif(jsn==jst)pd=1; %判断NL(S)=T?for(j=1:jsn)if(NlS(j)~=T(j))pd=0;break;end;end;endif(jsn==jst&pd)al=Inf; %如果NL(S)=T, 计算al, Inf为∞for(i=1:jss)for(j=1:n)pd=1;for(k=1:jst)if(T(k)==j)pd=0;break;end;endif(pd&al>L(S(i),1)+L(j,2)-A(S(i),j))al=L(S(i),1)+L(j,2)-A(S(i),j);end;end;end for(i=1:jss)L(S(i),1)=L(S(i),1)-al;end%调整可行点标记for(j=1:jst)L(T(j),2)=L(T(j),2)+al;end%调整可行点标记for(i=1:n)for(j=1:n) %生成子图GLif(L(i,1)+L(j,2)==A(i,j))Gl(i,j)=1;else Gl(i,j)=0;endM(i,j)=0;k=0;end;endii=0;jj=0;for(i=1:n)for(j=1:n)if(Gl(i,j))ii=i;jj=j;break;end;endif(ii)break;end;end%获得仅含Gl的一条边的初始匹配MM(ii,jj)=1;breakelse%NL(S)≠Tfor(j=1:jsn)pd=1;%取y∈NL(S)\Tfor(k=1:jst)if(T(k)==NlS(j))pd=0;break;end;endif(pd)jj=j;break;end;endpd=0;%判断y是否为M的饱和点for(i=1:n)if(M(i,NlS(jj)))pd=1;ii=i;break;end;endif(pd)jss=jss+1;S(jss)=ii;jst=jst+1;T(jst)=NlS(jj); %S=S∪{x}, T=T∪{y}else%获得Gl的一条M-增广路, 调整匹配Mfor(k=1:jst)M(S(k),T(k))=1;M(S(k+1),T(k))=0;endif(jst==0)k=0;endM(S(k+1),NlS(jj))=1;break;end;end;end;endMaxZjpp=0;for(i=1:n)for(j=1:n)if(M(i,j))MaxZjpp=MaxZjpp+A(i,j);end;end;endM %显示最佳匹配MMaxZjpp %显示最佳匹配M的权, 程序结束从一个可行流f 开始, 求最大流的Ford--Fulkerson 标号算法的基本步骤：⑴ 标号过程① 给发点v s 以标号(+, +∞) , δ s = +∞.② 选择一个已标号的点x , 对于x 的所有未给标号的邻接点y , 按下列规则处理：当yx ∈E , 且f yx ＞0时, 令δ y = min { f yx , δ x }, 并给y 以标号 ( x − , δ y ).当xy ∈E , 且f xy ＜C xy 时, 令δ y = min {C xy − f xy , δ x }, 并给y 以标号 ( x + , δ y ). ③ 重复②直到收点v t 被标号或不再有点可标号时为止. 若v t 得到标号, 说明存在一条可增广链, 转⑵调整过程; 若v t 未得到标号, 标号过程已无法进行时, 说明f 已经是最大流.⑵ 调整过程④ 决定调整量δ =δ vt , 令u = v t .⑤ 若u 点标号为( v +, δ u ), 则以f vu + δ 代替f vu ; 若u 点标号为( v −, δ u ), 则以 f vu − δ 代替f vu .⑥ 若v = v s , 则去掉所有标号转⑴重新标号; 否则令u = v , 转⑤.算法终止后, 令已有标号的点集为S , 则割集(S , S c )为最小割, 从而W f = C (S , S c ). 例1 求图6-19所示网络的最大流.利用Ford--Fulkerson 标号法求最大流算法的MATLAB 程序代码如下：n=8;C=[0 5 4 3 0 0 0 00 0 0 0 5 3 0 00 0 0 0 0 3 2 00 0 0 0 0 0 2 00 0 0 0 0 0 0 40 0 0 0 0 0 0 30 0 0 0 0 0 0 50 0 0 0 0 0 0 0]; %弧容量for (i=1:n)for (j=1:n)f(i,j)=0;end ;end %取初始可行流f 为零流for (i=1:n)No(i)=0;d(i)=0;end %No,d 记录标号图6-19while(1)No(1)=n+1;d(1)=Inf; %给发点vs标号while(1)pd=1;%标号过程for(i=1:n)if(No(i)) %选择一个已标号的点vifor(j=1:n)if(No(j)==0&f(i,j)<C(i,j)) %对于未给标号的点vj, 当vivj为非饱和弧时No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;if(d(j)>d(i))d(j)=d(i);endelseif(No(j)==0&f(j,i)>0) %对于未给标号的点vj, 当vjvi为非零流弧时No(j)=-i;d(j)=f(j,i);pd=0;if(d(j)>d(i))d(j)=d(i);end;end;end;end;endif(No(n)|pd)break;end;end%若收点vt得到标号或者无法标号, 终止标号过程if(pd)break;end%vt未得到标号, f已是最大流, 算法终止dvt=d(n);t=n; %进入调整过程, dvt表示调整量while(1)if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt; %前向弧调整elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvt;end%后向弧调整if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0; end;break;end%当t的标号为vs时, 终止调整过程t=No(t);end;end; %继续调整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);end%计算最大流量f %显示最大流wf %显示最大流量No %显示标号, 由此可得最小割, 程序结束设网络G = ( V , E , C ), 取初始可行流 f 为零流, 求解最小费用流问题的迭代步骤： ① 构造有向赋权图 G f = ( V , E f , F ), 对于任意的v i v j ∈E , E f , F 的定义如下：当f ij = 0时, v i v j ∈E f , F ( v i v j ) = b ij ;当f ij = C ij 时, v j v i ∈E f , F ( v j v i ) = −b ij ;当0＜ f ij ＜C ij 时, v i v j ∈E f , F ( v i v j ) = b ij , v j v i ∈E f , F ( v j v i ) = −b ij .转向②.② 求出有向赋权图G f = (V , E f , F )中发点v s 到收点v t 的最短路µ , 若最短路µ存在转向③; 否则f 是所求的最小费用最大流, 停止.③ 增流. 同求最大流的方法一样, 重述如下：令.,,,−+∈∈ −=µµδj i j i ij ij ij ij v v v v f f C δ = min {δ ij | v i v j ∈µ}, 重新定义流f = { f ij }为 f ij =,,,,−+∈∈ −+µµδδj i j i ijij ij v v v v f f f如果W f 大于或等于预定的流量值, 则适当减少δ 值, 使W f 等于预定的流量值, 那么 f 是所求的最小费用流, 停止; 否则转向①.求解含有负权的有向赋权图G = ( V , E , F )中某一点到其它各点最短路的Ford 算法. 当v i v j ∈E 时记w ij = F (v i v j ), 否则取w ii =0, w ij = +∞(i ≠j ). v 1到v i 的最短路长记为π ( i ), v 1到v i 的最短路中v i 的前一个点记为θ ( i ). Ford 算法的迭代步骤：① 赋初值π (1) = 0, π ( i ) = +∞, θ ( i ) = i , i = 2, 3, … , n .② 更新π ( i ), θ ( i ). 对于i = 2, 3, … , n 和j = 1, 2, … , n , 如果π ( i )＜π ( j ) + w ji , 则令π ( i ) = π ( j ) , θ ( i ) = j .　③　终止判断：若所有的π ( i )都无变化, 停止; 否则转向②.　在算法的每一步中, π ( i )都是从v 1到v i 的最短路长度的上界. 若不存在负长回路, 则从v 1到v i 的最短路长度是π ( i )的下界, 经过n −1次迭代后π ( i )将保持不变. 若在第n 次迭代后π ( i )仍在变化时, 说明存在负长回路.其它.例2 在图6-22所示运输网络上, 求s 到t 的最小费用最大流, 括号内为(C ij , b ij ).求最小费用最大流算法的MATLAB 程序代码如下：n=5;C=[0 15 16 0 00 0 0 13 140 11 0 17 00 0 0 0 80 0 0 0 0]; %弧容量b=[0 4 1 0 00 0 0 6 10 2 0 3 00 0 0 0 20 0 0 0 0]; %弧上单位流量的费用wf=0;wf0=Inf; %wf 表示最大流量, wf0表示预定的流量值for (i=1:n)for (j=1:n)f(i,j)=0;end ;end %取初始可行流f 为零流while (1)for (i=1:n)for (j=1:n)if (j~=i)a(i,j)=Inf;end ;end ;end %构造有向赋权图for (i=1:n)for (j=1:n)if (C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j);elseif (C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j);elseif (C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end ;end ;endfor (i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值for (k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路for (i=2:n)for (j=1:n)if (p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end ;end ;endif (pd)break ;end ;end %求最短路的Ford 算法结束if (p(n)==Inf)break ;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有向赋权图中不会含负权回路, 所以不会出现k=ndvt=Inf;t=n; %进入调整过程, dvt 表示调整量while (1) %计算调整量if (a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量elseif (a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量if (dvt>dvtt)dvt=dvtt;endif (s(t)==1)break ;end %当t 的标号为vs 时, 终止计算调整量t=s(t);end %继续调整前一段弧上的流fpd=0;if (wf+dvt>=wf0)dvt=wf0-wf;pd=1;end %如果最大流量大于或等于预定的流量值t=n;while (1) %调整过程if (a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt; %前向弧调整elseif (a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end %后向弧调整if (s(t)==1)break ;end %当t 的标号为vs 时, 终止调整过程t=s(t);endif (pd)break ;end %如果最大流量达到预定的流量值wf=0; for (j=1:n)wf=wf+f(1,j);end ;end %计算最大流量zwf=0;for (i=1:n)for (j=1:n)zwf=zwf+b(i,j)*f(i,j);end ;end %计算最小费用f %显示最小费用最大流图6-22wf %显示最小费用最大流量zwf %显示最小费用, 程序结束。

人狼羊菜渡河问题（含MATLAB程序）人、狼、羊、菜安全渡河问题安全过河问题也被称为“人狼羊菜”问题，具体描述为：一个人带着一只狼、一只羊和一篮白菜过河，但由于船太小，一个人一次只能带一件东西乘船过河。

狼和羊，羊和卷心菜不能单独呆在同一个河岸上，否则羊或卷心菜就会被吃掉。

这个问题可以用图论中的最短路径算法来解决。

问题分析根据题意，人不在场时，狼要吃羊，羊要吃菜，因此，人不在场时，不能将狼与羊、羊与菜留在河的任一岸。

可用四维向量v=（m，n，p，q）来表示状态，m表示人，n代表狼，p代表羊，q代表白菜，且m,n,p,q∈{0,1},0代表在对岸，1代表在此岸。

例如，状态（0,1,1,0）表示人和菜在对岸，而狼和羊在此岸，这时人不在场，狼要吃羊，因此，这个状态是不可行的。

通过穷举法列出所有可行状态。

可行状态是（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）。

有十种可行的状态。

每次过河行为都会改变现有状态。

构造了加权图G=（V，e，w），其中顶点集V={V1，？，V10}（按上述顺序编号）中的顶点分别代表上述10种可行状态。

当且仅当对应的两个可行状态之间存在可行转移时，两个顶点之间存在边连接，且对应的权重为1。

当两个顶点之间没有可行的过渡时，相应的权重可以取为∞.因此问题变为在图ｇ中寻找一条由初始状态（１,１,１,１）出发，经最小次数转移到达最终状态（０,０,０,０）的转移过程，即求从状态（１,１,１,１）到状态（０,０,０,０）的最短路径。

这个问题的难点是计算邻接矩阵。

由于轮渡一次改变现有状态，因此引入了四维状态转移向量来反映轮渡情况。

1表示过河，0表示不过河。

例如，（1,1,0,0）表示人们和狼一起过河。

状态转换只有四种情况，它们由以下向量表示：（1,0,0,0），（1,1,0,0），（1,0,1,0），（1,0,0,1）现在指定状态向量和转换向量之间的运算为0+0=0,1+0=1,0+1=1,1+1=0根据上述定义，如果从可行状态获得的新向量加上转移向量仍然属于可行状态，则对应于两个可行状态的顶点之间存在边。

超全的图论程序关注微信公众号“超级数学建模”，教你做有料、有趣的数模人程序一：可达矩阵算法function P=dgraf(A)n=size(A,1);P=A;for i=2:nP=P+A^i;endP(P~=0)=1;P;程序二：关联矩阵和邻接矩阵互换算法function W=incandadf(F,f)if f==0m=sum(sum(F))/2;n=size(F,1);W=zeros(n,m);k=1;for i=1:nfor j=i:nif F(i,j)~=0W(i,k)=1;W(j,k)=1;k=k+1;endendendelseif f==1m=size(F,2);n=size(F,1);W=zeros(n,n);for i=1:ma=find(F(:,i)~=0);W(a(1),a(2))=1;W(a(2),a(1))=1;endelsefprint('Please imput the right value of f');endW;程序三：有向图关联矩阵和邻接矩阵互换算法function W=mattransf(F,f)if f==0m=sum(sum(F));n=size(F,1);W=zeros(n,m);k=1;for i=1:nfor j=i:nif F(i,j)~=0W(i,k)=1;W(j,k)=-1;k=k+1;endendendelseif f==1m=size(F,2);n=size(F,1);W=zeros(n,n);for i=1:ma=find(F(:,i)~=0);if F(a(1),i)==1W(a(1),a(2))=1;elseW(a(2),a(1))=1;endendelsefprint('Please imput the right value of f'); endW;第二讲：最短路问题程序一：Dijkstra算法（计算两点间的最短路）function [l,z]=Dijkstra(W)n = size (W,1);for i = 1 :nl(i)=W(1,i);z(i)=0;endi=1;while i<=nfor j =1 :nif l(i)>l(j)+W(j,i)l(i)=l(j)+W(j,i);z(i)=j-1;if j<ii=j-1;endendendi=i+1;end程序二：floyd算法（计算任意两点间的最短距离）function [d,r]=floyd(a)n=size(a,1);d=a;for i=1:nfor j=1:nr(i,j)=j;endendr;for k=1:nfor i=1:nfor j=1:nif d(i,k)+d(k,j)<d(i,j)d(i,j)=d(i,k)+d(k,j); r(i,j)=r(i,k);endendendend程序三：n2short.m 计算指定两点间的最短距离function [P u]=n2short(W,k1,k2)n=length(W);U=W;m=1;while m<=nfor i=1:nfor j=1:nif U(i,j)>U(i,m)+U(m,j)U(i,j)=U(i,m)+U(m,j);endendendm=m+1;endu=U(k1,k2);P1=zeros(1,n);k=1;P1(k)=k2;V=ones(1,n)*inf;kk=k2;while kk~=k1for i=1:nV(1,i)=U(k1,kk)-W(i,kk);if V(1,i)==U(k1,i)P1(k+1)=i;kk=i;k=k+1;endendendk=1;wrow=find(P1~=0);for j=length(wrow):-1:1P(k)=P1(wrow(j));k=k+1;endP;程序四、n1short.m(计算某点到其它所有点的最短距离)function[Pm D]=n1short(W,k)n=size(W,1);D=zeros(1,n);for i=1:n[P d]=n2short(W,k,i);Pm{i}=P;D(i)=d;end程序五：pass2short.m(计算经过某两点的最短距离) function [P d]=pass2short(W,k1,k2,t1,t2)[p1 d1]=n2short(W,k1,t1);[p2 d2]=n2short(W,t1,t2);[p3 d3]=n2short(W,t2,k2);dt1=d1+d2+d3;[p4 d4]=n2short(W,k1,t2);[p5 d5]=n2short(W,t2,t1);[p6 d6]=n2short(W,t1,k2);dt2=d4+d5+d6;if dt1<dt2d=dt1;P=[p1 p2(2:length(p2)) p3(2:length(p3))]; elsed=dt1;p=[p4 p5(2:length(p5)) p6(2:length(p6))]; endP;d;第三讲：最小生成树程序一：最小生成树的Kruskal算法function [T c]=krusf(d,flag)if nargin==1n=size(d,2);m=sum(sum(d~=0))/2;b=zeros(3,m);k=1;for i=1:nfor j=(i+1):nif d(i,j)~=0b(1,k)=i;b(2,k)=j;b(3,k)=d(i,j);k=k+1;endendendelseb=d;endn=max(max(b(1:2,:)));m=size(b,2);[B,i]=sortrows(b',3);B=B';c=0;T=[];k=1;t=1:n;for i=1:mif t(B(1,i))~=t(B(2,i))T(1:2,k)=B(1:2,i);c=c+B(3,i);k=k+1;tmin=min(t(B(1,i)),t(B(2,i)));tmax=max(t(B(1,i)),t(B(2,i)));for j=1:nif t(j)==tmaxt(j)=tmin;endendendif k==nbreak;endendT;c;程序二：最小生成树的Prim算法function [T c]=Primf(a)l=length(a);a(a==0)=inf;k=1:l;listV(k)=0;listV(1)=1;e=1;while (e<l)min=inf;for i=1:lif listV(i)==1for j=1:lif listV(j)==0 & min>a(i,j)min=a(i,j);b=a(i,j);s=i;d=j;endendendendlistV(d)=1;distance(e)=b;source(e)=s;destination(e)=d;e=e+1;endT=[source;destination];for g=1:e-1c(g)=a(T(1,g),T(2,g));endc;另外两种程序最小生成树程序1（prim 算法构造最小生成树）a=[inf 50 60 inf inf inf inf;50 inf inf 65 40 inf inf;60 inf inf 52 inf inf 45;...inf 65 52 inf 50 30 42;inf 40 inf 50 inf 70 inf;inf inf inf 30 70 inf inf;...inf inf 45 42 inf inf inf];result=[];p=1;tb=2:length(a);while length(result)~=length(a)-1temp=a(p,tb);temp=temp(:);d=min(temp);[jb,kb]=find(a(p,tb)==d);j=p(jb(1));k=tb(kb(1));result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];endresult最小生成树程序2（Kruskal 算法构造最小生成树）clc;clear;a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70;[i,j,b]=find(a);data=[i';j';b'];index=data(1:2,:);loop=max(size(a))-1;result=[];while length(result)<looptemp=min(data(3,:));flag=find(data(3,:)==temp);flag=flag(1);v1=data(1,flag);v2=data(2,flag);if index(1,flag)~=index(2,flag)result=[result,data(:,flag)];endindex(find(index==v2))=v1;data(:,flag)=[];index(:,flag)=[];endresult第四讲：Euler图和Hamilton图程序一：Fleury算法（在一个Euler图中找出Euler环游）注：包括三个文件；fleuf1.m, edf.m, flecvexf.m function [T c]=fleuf1(d)%注：必须保证是Euler环游，否则输出T=0,c=0n=length(d);b=d;b(b==inf)=0;b(b~=0)=1;m=0;a=sum(b);eds=sum(a)/2;ed=zeros(2,eds);vexs=zeros(1,eds+1);matr=b;for i=1:nif mod(a(i),2)==1m=m+1;endendif m~=0fprintf('there is not exit Euler path.\n') T=0;c=0;endif m==0vet=1;flag=0;t1=find(matr(vet,:)==1);for ii=1:length(t1)ed(:,1)=[vet,t1(ii)];vexs(1,1)=vet;vexs(1,2)=t1(ii);matr(vexs(1,2),vexs(1,1))=0;flagg=1;tem=1;while flagg[flagg ed]=edf(matr,eds,vexs,ed,tem); tem=tem+1;if ed(1,eds)~=0 & ed(2,eds)~=0T=ed;T(2,eds)=1;c=0;for g=1:edsc=c+d(T(1,g),T(2,g));endflagg=0;break;endendendendfunction[flag ed]=edf(matr,eds,vexs,ed,tem)flag=1;for i=2:eds[dvex f]=flecvexf(matr,i,vexs,eds,ed,tem);if f==1flag=0;break;endif dvex~=0ed(:,i)=[vexs(1,i) dvex];vexs(1,i+1)=dvex;matr(vexs(1,i+1),vexs(1,i))=0;elsebreak;endendfunction [dvex f]=flecvexf(matr,i,vexs,eds,ed,temp) f=0;edd=find(matr(vexs(1,i),:)==1);dvex=0;dvex1=[];ded=[];if length(edd)==1dvex=edd;elsedd=1;dd1=0;kkk=0;for kk=1:length(edd)m1=find(vexs==edd(kk));if sum(m1)==0dvex1(dd)=edd(kk);dd=dd+1;dd1=1;elsekkk=kkk+1;endendif kkk==length(edd)tem=vexs(1,i)*ones(1,kkk);edd1=[tem;edd];for l1=1:kkklt=0;ddd=1;for l2=1:edsif edd1(1:2,l1)==ed(1:2,l2)lt=lt+1;endendif lt==0ded(ddd)=edd(l1);ddd=ddd+1;endendendif temp<=length(dvex1)dvex=dvex1(temp);elseif temp>length(dvex1) & temp<=length(ded)dvex=ded(temp);elsef=1;endend程序二：Hamilton改良圈算法（找出比较好的Hamilton路）function [C d1]= hamiltonglf(v)%d表示权值矩阵%C表示算法最终找到的Hamilton圈。