图论的有关算法.doc

《图论的有关算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、n=8;A=[0281infinfinfinf206inf1infinfinf8607512inf1inf70infinf9infinf15inf03inf8infinf1inf3046infinf29inf403infinfinfinf8630];%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)

2、i,j)end;end;end%k%显示迭代步数%D%显示每步迭代后的步长%R%显示每步迭代后的路径pd=0;for(i=1:n)%含有负权时if(D(i,j)<0)pd=1;break;end;end%存在一条含有顶点vi的负回路if(pd)break;end%存在一条负回路，终止程序end%程序结束D输出结果：D=0281InfInfInfInf206Inf1InfInfInf8607512Inf1Inf70InfInf9InfInf15Inf03Inf8InfInf1Inf3046InfInf29Inf403InfInfInfInf8630D=027136911205314797

3、50741251370479123144036864173036972963031195128630最小生成树算法代码：n=8;A=[0281000020601000860751201070009001500308001030460029040300008630];k=1;%记录A中不同正数的个数for(i=1:n-1)%此循环是查找A中所有不同的正数for(j=i+1:n)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;endk=k+kk;e

4、nd;end;endk=k-1;%显示A中所有不同正数的个数for(i=1:k-1)%将x中不同的正数从小到大排序for(j=i+1:k)if(x(j)

5、掉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中有圈elseq=q+1;end;end;end;end;endT%

6、显示近似最小生成树T，程序结束输出结果：T=0201000020001000000001201000000001000300001030000020000300000030匈牙利算法MATLAB程序：m=5;n=5;A=[0110011011011000110000011];M(m,n)=0;for(i=1:m)for(j=1:n)if(A(i,j))M(i,j)=1;break;end;endif(M(i,j))break;end;endwhile(1)for(i=1:m)x(i)=0;endfor(i=1:n)y(i)=0;endfor(i=1:m)pd=1;for(j=1:n)i

7、f(M(i,j))pd=0;end;endif(pd)x(i)=-n-1;end;endpd=0;while(1)xi=0;for(i=1:m)if(x(i)<0)xi=i;break;end;endif(xi==0)pd=1;break;endx(xi)=x(xi)*(-1);k=1;for(j=1:n)if(A(xi,j)&y(j)==0)y(j)=xi;yy(k)=j;k=k+1;end;endif(k>1)k=k-1;for(j=1:k