普利姆算法求最小生成树程序.doc

普利姆算法求最小生成树#include<>#include<>#include<>#include<>#include<>//定义各种数据类型最值常量#defineMAX_VERTEX_NUM20//最大顶点个数#defineMAX_NAME3//顶点值的最大字符个数#defineMAX_INFO20//边的相关信息的最大字符个数#defineINFINITYINT_MAX//最大值∞typedefintVRType;typedefcharInfoType;typedefcharVertexType[MAX_NAME];typedefintInfotype;#defineMAXV100/*定义邻接矩阵类型*/typedefstruct{ intno;//顶点编号 Infotypeinfo;//顶点其他信息}Vertextype;//顶点类型typedefstruct//图的定义{ intedges[MAXV][MAXV];//邻接矩阵 intvexnum,um;//定点数,弧数 Vertextypevexs[MAXV];//存放顶点信息}Graph;//图的邻接矩阵类型/*定义图的邻接表类型*/typedefstructANode//弧的结点结构类型{ intadjvex;//该弧所指向的顶点的位置 structANode*nextarc;//指向下一条弧的指针 Infotypeinfo;//该弧相关信息的指针}ode;typedefintVertex;typedefstructVnode//邻接表头结点的类型{ Vertexdata;//顶点信息 ode*firstarc;//指向第一条依附该顶点的弧的指针}VNode;typedefVNodeAdjList[MAXV];typedefstruct{ AdjListadjlist;//邻接表 intn,e;//图的当前顶点数和弧数}ALGraph;//图的邻接表类型#defineINF32767/*定义两个数组(邻接矩阵)储存元素的信息和元素之间的关系的信息*/typedefstruct{ VRTypeadj;//顶点关系类型;对带权图,为权值类型 InfoType*info;//该弧相关信息的指针}ell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{ VertexTypevexs[MAX_VERTEX_NUM];//顶点向量 AdjMatrixarcs;//邻接矩阵 intvexnum,um;//图的当前定点数和弧数}MGraph;/*记录从顶点集U到V-U的代价最小的边的辅助数组定义*/typedefstruct{ VertexTypeadjvex; VRTypelowcost;}minside[MAX_VERTEX_NUM];/*确定顶点在图中的位置*/intLocateVex(MGraphG,VertexTypeu){ inti; for(i=0;i<;++i) if(strcmp(u,[i])==0) returni;//存在返回顶点在图中的位置 return-1;//不存在返回其他信息}/*输入无向图的信息,构造无向