数据结构（C++语言版）.pptVIP

Prim算法的符号表示(1)U＝{u0}，T={}；(2)while(U≠V)do(u，v)＝min{wuv；u∈U，v∈V－U}T＝T＋{(u，v)}U＝U＋{v}(3)结束具体的操作示意图Prim算法的操作示意图动态过程Prim算法实现动态过程lowcostClosevertex从V0出发用Prim算法求最小生成树的过程i=1i=2i=3i=4i=5i=60123456kmincost05060∞∞∞∞00000000060∞∞65400001100150440006070∞500000414035000523042000034133005204200530003413364200450000006413324500000000064133#defineINFINITY30000//定义一个权值的最大值#defineMaxVertexNum30//最大顶点数为30typedefstruct{intadjvertex;//某顶点与已构造好的部分生成树的顶点之间权值最小的顶点intlowcost;//某顶点与已构造好的部分生成树的顶点之间的最小权值}ClosEdge;//定义普里姆算法求最小生成树时的辅助数组元素类型ClassMGragh{public:MGragh(){}//缺省构造函数voidCreatGraph();//建立图的存储矩阵成员函数voidMGragh::BFStraverse();//广度遍历图voidMGragh::BFS(intv);//从顶点v开始广度遍历图voidMiniSpanTree_PRIM(intu);Prim算法的C++实现：private:VertexTypevertexs[MaxVertexNum]；//顶点表Edgetypearcs[MaxVertexNum][MaxVertexNum]；//邻接矩阵，即边表intvertexNum,edgeNum；//顶点数和边数ClosEdgeclose_edge[MaxVertexNum];//存放最小生成树数组intvisited[MaxVertexNum];//访问标志数组}；Prim算法的C++实现：//MGragh是以邻接矩阵存储的图类voidMGragh::MiniSpanTree_PRIM(intu){//从第u个顶点出发构造图G的最小生成树,最小生成树顶点信息存放在数组close_edge中inti,j,w,k;for(i=0;ivertexNum;i++)//辅助数组初始化if(i!=u){close_edge[i].adjvertex=u;close_edge[i].lowcost=arcs[u][i];}close_edge[u].lowcost=0;//初始,U={u}for(i=0;ivertexNum-1;i++)//选择其余的G.vertexNum-1个顶点{w=INFINITY;for(j=0;jvertexNum;j++)//在辅助数组close_edge中选择权值最小的顶点if(close_edge[j].lowcost!=0close_edge[j].lowcostw){w=close_edge[j].lowcost;k=j;}//求出生成树的下一个顶点kclose_edge[k].lowcost=0;//第k个顶点并入U集for(j=0;jvertexNum;j++)//新顶点并入U后,修改辅助数组if(arcs[k][j]close_edge[j].lowcost){close_edge[j].adjvertex=k;close_edge[j].lowcost=arcs[k][j];