最小生成树prim、

过年那几天确实没好好学习、在老家闲着也是闲着、可是就是没看书、

回来这几天又一直在弄个人博客、买域名云服务器备案什么的- -、麻烦死了呢、

在腾讯花1块钱备案了一个网站www.goodgoodstudy.pw，起名字的时候实在是纠结，索性来了个无聊的

备案完成后还是决定在阿里云再备案一个网站，我也说不上原因- - 、先凑合着用吧

最小生成树prim算法、

 //prim算法生成最小生成树

 void prim(MGriph G)

 {

     int minx,k;

     sum=;

     memset(vis,false,sizeof(vis));    //初始化访问顶点数组

     vis[]=true;                    //将顶点Vo加入到最小生成树中、

     for(int i=;i<numVertexes;++i)    //初始化当前的最小生成树的最小权值数组

         lowcost[i]=map[][i];

     for(int i=;i<numVertexes;++i){

         minx=INT_MAX;

         for(int j=;j<numVertexes;++j)        //寻找当前的最小权值顶点、

             if(!vis[j] && minx > lowcost[j])

                 minx = lowcost[k = j];

         if(minx==INT_MAX)    break;

         vis[k]=ture;    //将最小权值顶点加入最小生成树集合 、

         sum+=minx;        // 记录权值的和、

         for(int j=;j<numVertexes;++j)        //更新当前最小生成数中的最小权值数组、

             if(!vis[j] && lowcost[j] > map[k][j])

                 lowcost[j] = map[k][j];

     }

 }

要理解代码最主要是要理解lowcost数组和vis数组的作用，vis数组的话是记录当前最小生成树的顶点数，当vis[i]=ture的时候代表Vi顶点已经加入到最小生成树中来了，否者没有，lowcost数组的作用呢就是记录当前最小生成树中各顶点与其有边的顶点间的最小权值

这是我对这段代码的理解、

巴特西

最小生成树prim、

最新文章

热门文章