第16章图论模型及其算法.ppt

例3 用Floyd算法求出例1中任意两个城市间最便宜的航行路线。 Matlab算法如下： clear; clc; M=10000; a(1,:)=[0,50,M,40,25,10]; a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M]; a(4,:)=[zeros(1,4),10,25]; a(5,:)=[zeros(1,5),55]; a(6,:)=zeros(1,6); b=a+a;path=zeros(length(b)); for k=1:6 for i=1:6 for j=1:6 if b(i,j)b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j); path(i,j)=k; end end end end b, path 运行结果为： b = 0 35 45 35 25 10 35 0 15 20 30 25 45 15 0 10 20 35 35 20 10 0 10 25 25 30 20 10 0 35 10 25 35 25 35 0 path = 0 6 5 5 0 0 6 0 0 0 4 0 5 0 0 0 0 4 5 0 0 0 0 0 0 4 0 0 0 1 0 0 4 0 1 0 3.1 基本概念 3.2 最小生成树 欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为Cij，设计一个线路图，使总造价最低。连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具有最小权的生成树叫做最小生成树。 1)prim算法 构造最小生成树的两种常用算法：prim算法和Kruskal算法。 例4 用prim算法求图16-9的最小生成树。 图16-9 连通的无向图 解：用矩阵result3×n的第一、二、三行分别表示生成树边的起点、终点、权集合。 Matlab程序如下： clc;clear; M=1000; 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; a=[a;zeros(2,7)]; a=a+a;a(find(a==0))=M; result=[];p=1;tb=2:length(a); while length(result)~=length(a)-1 temp=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))=[]; end result 运行结果为： result = 1 2 5 4 4 7 2 5 4 6 7 3 50 40 50 30 42 45 最小生成树如图16-10. 图16-10 最小生成树 2) Kruskal算法 例5 利用Kruskal算法计算例4的最小生成树。 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)loop temp=min(data(3,: )); flag=find(data(3,: )==temp); flag=flag(1); v1=data(1,flag); v2=data(2, flag); if index(1