图论算法及其matlab程序代码

《图论算法及其matlab程序代码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论算法及其MATLAB程序代码求赋权图G=(V,E,F)中任意两点间的最短路的Warshall-Floyd算法：设A=(aij)n×n为赋权图G=(V,E,F)的矩阵,当vivj∈E时aij=F(vivj),否则取aii=0,aij=+∞(i≠j),dij表示从vi到vj点的距离,rij表示从vi到vj点的最短路中一个点的编号.①赋初值.对所有i,j,dij=aij,rij=j.k=1.转向②②更新dij,rij.对所有i,j,若dik+dkj＜dij,则令dij=dik+dkj,rij=k,转向③.③

2、终止判断.若dii＜0,则存在一条含有顶点vi的负回路,终止;或者k=n终止;否则令k=k+1,转向②.最短路线可由rij得到.例1求图6-4中任意两点间的最短路.图6-4解：用Warshall-Floyd算法,MATLAB程序代码如下：n=8;A=[0281InfInfInfInf206Inf1InfInfInf8607512Inf1Inf70InfInf9InfInf15Inf03Inf8InfInf1Inf3046InfInf29Inf403InfInfInfInf8630];%MATLAB中,In

3、f表示∞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)

4、点vi的负回路if(pd)break;end%存在一条负回路,终止程序end%程序结束Kruskal避圈法：将图G中的边按权数从小到大逐条考察,按不构成圈的原则加入到T中(若有选择时,不同的选择可能会导致最后生成树的权数不同),直到q(T)=p(G)-1为止,即T的边数=G的顶点数-1为止.Kruskal避圈法的MATLAB程序代码如下：n=8;A=[0281000020601000860751201070009001500308001030460029040300008630];k=1;%记录A中不同正

5、数的个数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)

6、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;en

7、d;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中有圈elseq=q+1;end;end;end;end;endT%显示近似最小生成树T,程序结束求二部图G

8、的最大匹配的算法(匈牙利算法),其基本思想是：从G的任意匹配M开始,对X中所有M的非饱和点,寻找M-增广路.若不存在M-增广路,则M为最大匹配;若存在M-增广路P,则将P中M与非M的边互换得到比M多一边的匹配M1,再对M1重复上述过程.设G=(X,Y,E)为二部图,其中X={x1,x2,…,xn},Y={y1,y2,…,yn}.任取G的一初始匹配M(如任取e∈E,则M={e}是一个匹配).①令S=f,T=f,转向②.②若M饱和