用c++实现的无向图广度优先遍历

《用c++实现的无向图广度优先遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、用C++实现的实现无向图的广度优先遍历#include#includeusingnamespacestd;//图的邻接表存储表示#defineMAX_NAME5//顶点字符串的最大长度#defineMAX_VERTEX_NUM20typedefcharVertexType[MAX_NAME];typedefstructArcNode{//表结点intadjvex;structArcNode*nextarc;int*info;}ArcNode;typedefstructVNode{//头结点VertexTypedata;ArcNode*firsta

2、rc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{//图AdjListvertices;intvexnum,arcnum;stringkind;}ALGraph;//队列的链式存储结构P61(元素类型为整形)typedefstructQNode{intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;intInitQueue(LinkQueue&Q)//构造一个空队列{Q.front

3、=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(-1);//存储分配失败Q.front->next=NULL;return1;}boolQueueEmpty(LinkQueueQ)//判空{if(Q.front==Q.rear)returntrue;returnfalse;}intEnQueue(LinkQueue&Q,inte)//队列的插入（尾）{QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(-1);//存储分配失败p->data=e;p->next

4、=NULL;Q.rear->next=p;Q.rear=p;//尾指针后移return1;}intDeQueue(LinkQueue&Q,int&e)//队列的删除（首）{QueuePtrp;if(Q.front==Q.rear)return0;//队列空，返回0p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;//尾指针回送free(p);return1;}intLocateVex(ALGraphG,VertexTypeu)//返回顶点在图中的位置，无则返回-1{for(inti

5、=0;i>G.kind;cout<<"请输入图的顶点数,边数:";cin>>G.vexnum>>G.arcnum;cout<<"请输入各个顶点的值";for(inti=0;i

6、/构造顶点向量{cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;}if(G.kind=="DN"

7、

8、G.kind=="UDN")//网cout<<"请顺序输入每条弧(边)的弧尾、弧头及权值:";elsecout<<"请顺序输入每条弧(边)的弧尾和弧头:";for(intk=0;k

9、

10、G.kind=="UDN")cin>>va>>vb>>w;elsecin>>va>>vb;inti=LocateVex(G,va);//弧尾intj=Locate

11、Vex(G,vb);//弧头p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;if(G.kind=="DN"

12、

13、G.kind=="UDN"){p->info=(int*)malloc(sizeof(int));*(p->info)=w;}elsep->info=NULL;p->nextarc=G.vertices[i].firstarc;//插在表头G.vertices[i].firstarc=p;if(G.kind=="