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

《普利姆算法求最小生成树程序.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、普利姆算法求最小生成树#include#include#include#include#include//定义各种数据类型最值常量#defineMAX_VERTEX_NUM20//最大顶点个数#defineMAX_NAME3//顶点值的最大字符个数#defineMAX_INFO20//边的相关信息的最大字符个数#defineINFINITYINT_MAX//最大值∞typedefintVRType;typedefcharInfoType;typedefcharVerte

2、xType[MAX_NAME];typedefintInfotype;#defineMAXV100/*定义邻接矩阵类型*/typedefstruct{intno;//顶点编号Infotypeinfo;//顶点其他信息}Vertextype;//顶点类型typedefstruct//图的定义{intedges[MAXV][MAXV];//邻接矩阵intvexnum,arcnum;//定点数，弧数Vertextypevexs[MAXV];//存放顶点信息}Graph;//图的邻接矩阵类型/*定义图的邻接表类型*/typedefstructANode//弧的结点结构类型{

3、intadjvex;//该弧所指向的顶点的位置structANode*nextarc;//指向下一条弧的指针Infotypeinfo;//该弧相关信息的指针}ArcNode;typedefintVertex;typedefstructVnode//邻接表头结点的类型{Vertexdata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode;typedefVNodeAdjList[MAXV];typedefstruct{AdjListadjlist;//邻接表intn,e;//图的当前顶点数和弧数}ALGraph;//图的邻接

4、表类型#defineINF32767/*定义两个数组（邻接矩阵）储存元素的信息和元素之间的关系的信息*/typedefstruct{VRTypeadj;//顶点关系类型；对带权图，为权值类型InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前定点数和弧数}MGraph;/*记录从顶点

5、集U到V-U的代价最小的边的辅助数组定义*/typedefstruct{VertexTypeadjvex;VRTypelowcost;}minside[MAX_VERTEX_NUM];/*确定顶点在图中的位置*/intLocateVex(MGraphG,VertexTypeu){inti;for(i=0;i

6、w,IncInfo;chars[MAX_INFO],*info;VertexTypeva,vb;printf("请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0):(空格区分)");scanf("%d%d%d%*c",&(*G).vexnum,&(*G).arcnum,&IncInfo);printf("请输入%d个顶点的值(<%d个字符):",(*G).vexnum,MAX_NAME);for(i=0;i<(*G).vexnum;++i)//构造顶点向量scanf("%s",(*G).vexs[i]);for(i=0;i<(*G).vexnum;

7、++i)//初始化邻接矩阵for(j=0;j<(*G).vexnum;++j){(*G).arcs[i][j].adj=INFINITY;(*G).arcs[i][j].info=NULL;}printf("请输入%d条边的顶点1顶点2权值(以空格作为间隔):",(*G).arcnum);for(k=0;k<(*G).arcnum;++k)//构造邻接矩阵{scanf("%s%s%d%*c",va,vb,&w);i=LocateVex(*G,va);j=LocateVex(*G,vb);(*G).arcs[i][j].adj=(*G).arcs[j][i].