普里姆算法应用场景
假设阿、b、c、d、e、f、g为7个城市，为便利生产生活，将建立这7个城市的通信。 对7个城市来说，根据节约经费的原则，只需制作6条通信线路就可以达到修路问题的本质就是最小生成树问题，简称MST
给出加权无向连通图，如何选择生成树使树所有边的权重总和最小。 将其称为最小生成树的n个顶点，必须有n-1条边位于所有顶点普里姆算法
将g=(v，e )作为连接网，t=) u，d )作为最小生成树，将v，u作为顶点集合，将e，d作为边的集合，从顶点u中生成最小生成树，从集合v中取出顶点u并放入集合中，标记顶点v的visited
publicclassprimalgorithm { publicstaticvoidmain (string [ ] args ) {char[] data={'A '、' b '、' c、' d、' e、} int [ ] [ ] weight={ 10000，5，7，10000，10000，2 }、{ 5，10000，10000，9，10000，10000，10000，3 }、{ 5。 10000，5，4 }，{ 10000，10000，10000，10000，4，5，10000 } mgraphgraph=newmgraph (ver xs )； 最小树最小树=新树(； mintree.creategraph(graph，verxs，data，weight )； mintree.showgraph(graph； mintree.prim(graph，3 )； } classmintree { publicvoidcreategraph (mgraphgraph，int verxs，char data[]，int ) ) weight ) ) {int i； int j； for(I=0； i verxs； I )//顶点graph.data[i]=data[i]； for(j=0； j verxs； j ) graph.weight [ I ] [ j ]=weight [ I ] [ j ]； }/****prim算法* @param graph图* @从* @param v开始的顶点*/publicvoidprim(mgraph，int v ) (/标记顶点访问int[]visited=new//用h1和h2记录两个顶点的下标int h1=-1，int h2=-1； int minWeight=10000； 最大限度地初始化最小权重，后面的变量替换为for (intk=1； k graph.verxs； 由于有k () graph.verxs的顶点，勇敢中心算法得到胡搜索后，graph.verxs-1的边for(intI=0； i graph.verxs； I () /被访问的顶点for(intj=0； j graph.verxs； j ) ) /未访问的顶点if (visited [ I ]==1visited [ j ]==0graph.weight [ I ] [ j ] min weight ) (/minweight (改为h1=i h2=j； }//找到边最小的System.out.println (边' graph.data[h1]，' graph.data[h2] )权重： ' minWeight ' ) 最小权重=10000； } publicvoidshowgraph (mgraphgraph ) for ) intI=0； i graph.verxs； I ) for(intj=0； j graph.verxs； j ) (system.out.print ) graph.weight[I][j] ' )； }System.out.println (； }}}class MGraph {int verxs； //图中的节点数char[] data； //保存节点的数据int[][] weight； //相邻矩阵publicmgraph(intverxs ) {this.verxs=verxs； data=new char[verxs]； weight=new int[verxs][verxs]； }