图解
代码实现package com.atguigu.prim； import java.util.Arrays； /** * @作者wdl * @创建时间2021/4/5 * @说明*/publicclassprimalgorithm { publicstaticvoidmain (string [ ] args )//测试图//相邻矩阵由二维阵列表示，并且对于10000这个较大的数，这两个点是int [ ] [ ] weight=new int [ ] { { 10000，5，7，10000，10000，10000，10000，2 10000、10000、10000、4，10000 }、{ 10000、10000、8，10000、10000、5，4 }、{ 10000，1000 } m graph对象mgraph mintree.creategraph(graph，verxs，data，weight )； 输出//mintree.showgraph(graph )； //棱镜算法mintree.prim(graph， 测试0 ) }//最小生成树-创建村图class MinTree{ //创建贴图的邻接矩阵/** * * @param graph贴图对象* @param verxs贴图对应的顶点数*/@param weight贴图的相邻publicvoidcreategraph (mgraphgraph，int verxs，char data[]，int[][] weight ) { int i，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 ]； }//图的邻接矩阵publicvoidshowgraph (mgraphgraph ) for ) int[]link:graph.weight ) system.out.println ) Arrays }//创建//visited[]的默认设置，用于指示从地图的第几个顶点生成' a '-0 ' b '-1 . * /公共void prim (mgraphgraph，mgraph ) i graph.verxs； I ) {//visited[i]=0； //当前将此节点标记为已访问visited[v]=1； //h1和h2记录两个顶点的下标int h1=-1； int h2=-1； int minWeight=10000； 最初将最小权重设置为较大的数字，然后在遍历过程中输入for(intk=1； k graph.verxs； 因为有k () graph.verxs的顶点，所以prime算法结束后，有graph.verxs-1边) /这样的每次生成时决定的子图，与哪个节点的距离最近是for(intI=0； i graph.verxs； I ()/I节点由被访问的节点for(intj=0； j graph.verxs； j ()/j节点是环未接入的节点if (visited [ I ]==1visited [ j ]==0graph.weight [ I ] [ j ] minweight ) /替换min weight h2=j； }//找出一边是最小的System.out.println (边' graph.data[h1]，' graph.data[h2] )权重： ' minWeight ' )//当前//最小权重重置为最大值10000 minWeight=10000； } }}class MGraph{ int verxs； //图中的节点数char[] data； //存储节点数据的int [][] weight； //保管边是我们的邻接矩阵publicmgraph(intverxs ) { this.verxs=verxs； data=new char[verxs]； weight=new int[verxs][verxs]； }