邻接表prim算法教案资料.doc

《邻接表prim算法教案资料.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、邻接表prim算法精品文档#include#include#defineMAX_VERTEX_NUM20#defineMAX32767#defineERROR0#defineOK1#defineOVERFLOW-2typedefintStatus;typedefcharVertexType;typedefintPathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefintShortPathTable[MAX_VERTEX_NUM];boolvisited[MAX_VERTEX_NUM];boolfinal[M

2、AX_VERTEX_NUM];typedefstruct{charadj;intlowcost;}closedge[MAX_VERTEX_NUM];typedefstructArcNode{intadjvex;//弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针intweight;//权重//InfoType*info;//该弧相关信息的指针}ArcNode;typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstr

3、uct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;//--------------------------------------------------//队列typedefstructnode{intdata;structnode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;//构造一个空队列收集于网络，如有侵权请联系管理员删除精品文档StatusInitQueue(LinkQueue&Q){Q.front=Q.rear=(Q

4、ueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;returnOK;}//插入元素StatusEnQueue(LinkQueue&Q,int&e){QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}//出队列StatusDeQueue(LinkQueue&Q,int&e){QueuePtrp;if(

5、Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(p==Q.rear)Q.rear=Q.front;free(p);returnOK;}StatusQueueEmpty(LinkQueue&Q){if(Q.front==Q.rear)returnOK;elsereturnERROR;}/*--------------------------------------------------*/intLocateVex(ALGraphG,chare){inti;for(i=0;i

6、exnum;i++)if(e==G.vertices[i].data)returni;return-1;}//创建图intCreateGraph(ALGraph&G){inti,j,w,k;charV1,V2;printf("输入顶点数，弧数：");scanf("%d%d",&G.vexnum,&G.arcnum);for(i=0;i

7、arc=NULL;}ArcNode*p;for(i=0;iadjvex=k;p->weight