图的深度遍历和广度遍历以及最小生成树

《图的深度遍历和广度遍历以及最小生成树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、//本程序主要包含以下功能//采用邻接矩阵构造图//图的深度遍历和广度遍历//采用普里姆算法和克鲁斯卡尔算法构造最小生成树#include#include#defineINFINITY999#defineMAX_VERTEX_NUM20#defineOK1#defineERROR-1typedefcharVertexType;typedefcharInfoType;typedefVertexTypeQElemType;boolvisited[MAX_VERTEX_NUM];//访问标志数组typedefstru

2、ct{/*辅助数组*/VertexTypeadjvex;intlowcost;}closedge[MAX_VERTEX_NUM];typedefstruct{intbegin;intend;intflag;intweight;}edge;edgeedges[50];typedefstructArcCell{intadj;InfoType*info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];AdjMat

3、rixarcs;intvexnum,arcnum;}MGraph;typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;intInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)returnERROR;Q.front->next=NULL;returnOK;

4、}intDestroyQueue(LinkQueue&Q){while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}//DestroyQueueintEnQueue(LinkQueue&Q,QElemTypee){QueuePtrp;//p=(QueuePtr)malloc(sizeof(QNode));if(!p)returnERROR;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}i

5、ntDeQueue(LinkQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;QueuePtrp;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}intQueueEmpty(LinkQueueQ){if(Q.rear==Q.front)return1;elsereturn0;}intLocateVex(MGraphG,VertexTypeu){inti;fo

6、r(i=0;i=0&&k=0&&i=0&&j

7、um){//i,j合理for(intk=j+1;k

8、char()!!!***///scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo)