资源描述:
《邻边矩阵求最小生成树》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、n=input('请输入图的顶点数目:n=');请输入图的顶点数目:n=8>>W=input('请输入图的加权邻矩阵:[W(1,1),..,W(1,n),..,W(n,n)]=');请输入图的加权邻矩阵:[W(1,1),..,W(1,n),..,W(n,n)]=[inf,7,8,2,inf,inf,3,inf;7,inf,1,inf,2,inf,inf,3;8,1,inf,4,2,7,inf,inf;2,inf,4,inf,inf,4,6,inf;inf,2,2,inf,inf,5,inf,1;inf,inf,7,4,5,inf,4,3;3
2、,inf,inf,6,inf,4,inf,6;inf,3,inf,inf,1,3,6,inf]>>>>T=zeros(n);WW=W;fori=1:n;forj=1:n;ifW(i,j)==infWW(i,j)=0;endendendm=((nnz(WW))/2);j=0j=0fori=1:mif(j3、2,m);y=0;fori=1:nforv=(i+1):nifT(i,v)~=0y=y+1;P(1,y)=i;P(2,y)=v;endendendfory=1:mifP(1,y)
4、P(2,l)=P(2,y);endendP(1,y)=P(2,y);elseif(P(1,y)+P(2,y))~=0f=1;breakendendiff==1T(a,b)=0;T(b,a)=0;elsej=j+1;endW(a,b)=inf;elseMST=T;input('这个图的最小生成树的加权邻接矩阵是:')MSTbreakendendifj<(n-1)input('这个图没有最小生成树.')j=0j=0这个图的最小生成树的加权邻接矩阵是:MST=00020030001000000100200020000000002000010000
5、00433000040000001300