prim算法

prim算法构造最小生成树构造赋权图(,,)GVEW，其中12n{,,,}Vvvv为顶点集合,其中iv表示第i个顶点，（E为边的集合），()ijnnWw为邻接矩阵，其中ijijijijvvvvwvv顶点与之间的距离，当（，）E，与之间没有边时prim算法如下：（1）初始化，构造1{}Pv，即选中顶点1v作为构造最小生成树的起点，构造空集Q。（2）找出权重最小的边pv，其中,VPpPv；把选中的顶点v加入集合P，{}PPv；把选中的边pv加入集合Q，{}QQpv；（3）当PV时终止，否则转入（2）已知9个村庄之间的两两距离见表5，要架设通讯线路把9个村庄连接起来，求所需要通讯线的最小长度。表510个村庄的两两距离数据（单位：km）12345678912118.614014.11775.56068.456012.750119.320119.43826.521819.5295216.80456.270210.748218.651816.675319.351914.49194.5714316.123815.890110.275614.48766.739015.29674.5093415.11739.073619.20364.551111.019910.1049514.341015.349816.07508.416414.8752613.36437.581016.02038.081578.120117.45158.068589.626617.293394.8632解：这是一个最小生成树问题，构造赋权图(,,)GVEW，其中129{,,,}Vvvv为顶点集合,其中iv表示第i个村庄，E为边的集合，99()ijWw为邻接矩阵，其中ijijijijvvvvwvv村庄与之间的距离，当（，）E，与之间没有通讯路线时利用prim算法求解出最小生成树：（1）初始化，构造1{}Pv，即选中村庄1v作为构造最小生成树的起点，构造空集Q。（2）找出距离最小的通讯线路pv，其中,VPpPv；把选中的顶点v加入集合P，{}PPv；把选中的边pv加入集合Q，{}QQpv；（3）当PV时终止，否则转入（2）通过Matlab程序画出9个村庄之间的连通图如图1，Nodei表示第i个村庄：14.11775.56066.27028.45610.748215.890112.750118.651810.27569.073619.320116.675314.487619.203615.349819.438219.35196.7394.551116.0757.5816.521814.491915.296711.01998.416416.020317.4515Node1Node2Node3Node4Node5Node6Node7Node8图1各村庄之间的连通情况5.56066.27026.7394.55117.5816.52188.4164Node1Node2Node3Node4Node5Node6Node7Node8图2各村庄之间的最小生成树通过Matlab计算，各村庄之间的最短通讯线的最小长度L=45.6401km。一、连通图程序clc,cleara=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([cz,int2str([1:9]')])%未改完view(biograph(b,v,'ShowArrows','off','ShowWeights','on'))