图与网络方法建模7.4天然气管道铺设方案.pptVIP

Kruskal算法的MATLAB程序kruskal.m如下： % Kruskal’s Algorithm function [T, c]= kruskal (b,n) % b为边权矩阵，第一、二行分别存放各条边的起点和终点，第三行存放各条边上的权 % n为图的顶点个数 % T为所求最小生成树的边集合，即给出各边所在的顶点 % c为所求最小生成树的总权大小 [B, i ]=sortrows(b’,3); B=B’; m=size(b,2); t=1:n; k=0; T=[ ]; c=0; for i=1:m if t (B(1,i))~=t (B(2,i)) k=k+1; T(k,1)=B(1,i); T(k,2)=B(2,i);c=c+B(3,i); tmin=min(t(B(1,i)), t(B(2,i))); tmax=max(t(B(1,i)), t(B(2,i))); for j=1:n if t(j)==tmax t(j)=tmin; end end end if k==n-1 break; end end 例如，用Kruskal算法求图1的最小生成树及相应的总权大小。 先建立M文件kruskal.m，然后在MATLAB命令窗口键入： n=5; b=[1 1 2 2 2 2 3 3 3 3 4 4 4 5 5 5;2 3 1 3 4 5 1 2 4 5 2 3 5 2 3 4;1 2 1 2 4 3 2 2 4 4 4 4 2 3 4 2]; [T, c]= kruskal (b,n) Prim算法的MATLAB程序prim.m如下： % Prim’s Algorithm function [T, c]= prim (a,n) % a为带权邻接矩阵 % n为图的顶点个数 % T为所求最小生成树的边集合，即给出各边所在的顶点 % c为所求最小生成树的总权大小 T=[ ]; c=0; v=1; sb=2:n; for j=2:n b(1,j-1)=1; b(2,j-1)=j; b(3,j-1)=a(1,j); end while size(T,2)n-1 [minss,i]=min(b(3,: )); T(:,size(T,2)+1)=b(:,i); c=c+b(3,i); v=b(2,i); temp=find(sb==b(2,i)); sb(temp)=[ ]; b(:,i)=[ ]; for j=1:length(sb) d=a(v,b(2,j)); if db(3,j) b(1,j)=v; b(3,j)=d; end end end 例如，用Prim算法求图1的最小生成树及相应的总权大小。 先建立M文件prim.m，然后在MATLAB命令窗口键入： n=5; a=[0 1 2 inf inf;1 0 2 4 3 ;2 2 0 4 4 ;inf 4 4 0 2 ;inf 3 4 2 0]; [T, c]= prim (a,n)