prim算法.doc

prim 算法构造最小生成树构造赋权图，其中为顶点集合,其中表示第 个顶点，（为边的集合），为邻接矩阵，其中prim 算法如下：（1）初始化，构造，即选中顶点作为构造最小生成树的起点，构造空集。（2）找出权重最小的边，其中； 把选中的顶点加入集合，； 把选中的边加入集合， ；（3）当时终止，否则转入（2）已知9个村庄之间的两两距离见表5，要架设通讯线路把9个村庄连接起来，求所需要通讯线的最小长度。表5 10个村庄的两两距离数据（单位：km）12345678912118.6140 14.1177 5.5606 8.4560 12.7501 19.3201 19.4382 6.5218 19.5295 216.8045 6.2702 10.7482 18.6518 16.6753 19.3519 14.4919 4.5714 316.1238 15.8901 10.2756 14.4876 6.7390 15.2967 4.5093 415.1173 9.0736 19.2036 4.5511 11.0199 10.1049 514.3410 15.3498 16.0750 8.4164 14.8752 613.3643 7.5810 16.0203 8.0815 78.1201 17.4515 8.0685 89.6266 17.2933 94.8632 解：这是一个最小生成树问题，构造赋权图，其中为顶点集合,其中表示第个村庄，为边的集合，为邻接矩阵，其中利用prim 算法求解出最小生成树 ：（1）初始化，构造，即选中村庄作为构造最小生成树的起点，构造空集。（2）找出距离最小的通讯线路，其中； 把选中的顶点加入集合，； 把选中的边加入集合， ；（3）当时终止，否则转入（2）通过Matlab程序画出9个村庄之间的连通图如图1，Node 表示第个村庄：图1 各村庄之间的连通情况图2 各村庄之间的最小生成树通过Matlab计算，各村庄之间的最短通讯线的最小长度L = 45.6401km。一、连通图程序clc,clear a=zeros(9); %邻接矩阵初始化a=xlsread(data.xls,B2:J10);a(isnan(a)=0;a=a; b=sparse(a) %变成下三角矩阵，并转化为稀疏矩阵 h=biograph(b,ShowWeights,on,ShowArrows,off) %生成图形对象 %Matlab2014B 和2015A,ShowWeights有bug,属性值为off时没有问题，属性值为on时出错， 但图形显示是正确的 set(h,LayoutType,equilibrium); %设置属性:图形的布局是平衡的 view(h) %显示图形二、最小生成树程序clc, cleara=zeros(9);a=xlsread(data.xls,B2:J10);a(isnan(a)=0;a=a; a=sparse(a);b=graphminspantree(a,Method,Prim)L=sum(sum(b)cu=cz=repmat(cu,9,1)v=cellstr(