广度优先搜索遍历连通图.docx

《广度优先搜索遍历连通图.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、韩山师范学院实验题目：用邻接表实现广度优先搜索遍历连通图的算法实现班级：2015级软工班作者：黄俊聪#includeusingnamespacestd;#defineMVNum100//最大顶点数#defineOK1#defineERROR0typedefintStatus;typedefcharVerTexType;typedefintOtherInfo;boolvisited[MVNum];typedefstructArcNode//边结点{intadjvex;//该边所指向的顶点的位置structArcNode*nextar

2、c;//指向下一条边的指针OtherInfoinfo;//和边相关的信息}ArcNode;typedefstructVNode//顶点信息{VerTexTypedata;ArcNode*firstarc;//指向第一条依附该顶点的边的指针}VNode,AdjList[MVNum];//Adjlist表示邻接表类型typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数}ALGraph;typedefstructQNode{chardata;structQNode*next;}QNode,*Que

3、uePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;StatusInitQueue(LinkQueue&Q){Q.front=Q.rear=newQNode;Q.front->next=NULL;returnOK;}StatusEnQueue(LinkQueue&Q,inte){QueuePtrp;p=newQNode;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}StatusQueueEmpty(LinkQueue&Q

4、){if(Q.front==Q.rear)returnOK;elsereturnERROR;}charDeQueue(LinkQueue&Q,int&e){QueuePtrp;if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;deletep;returnOK;}StatusLocateVex(ALGraphG,charv){inti;for(inti=0;i

5、(G.vertices[i].data==v)returni;returnERROR;}StatusCreateUDG(ALGraph&G){ArcNode*p1,*p2;charv1,v2;inti,j;cout<<"输入总顶点数和总边数："<>G.vexnum>>G.arcnum;//输入总顶点数和总边数cout<<"输入各点，构造表头结点表："<>G.vertices[i].data;//输入顶点值G.vertices[i].firstarc=NULL

6、;//初始化表头结点的指针域为NULL}cout<<"输入各边，构造邻接表："<>v1>>v2;//输入一条边依附的两个顶点i=LocateVex(G,v1);j=LocateVex(G,v2);//确定v1和v2在G中的位置，即顶点在G.vertices中的序号p1=newArcNode;//生成一个新的边结点*p1p1->adjvex=j;//邻接点序号为jp1->nextarc=G.vertices[i].firstarc;G.vertices[i

7、].firstarc=p1;//将新结点*p1插入顶点v1的边表头部p2=newArcNode;//生成另一个对称的新的边结点*p2p2->adjvex=i;//邻接点序号为ip2->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p2;//将新结点*p1插入顶点v1的边表头部}returnOK;}StatusFirstAdjVex(ALGraphG,intv){ArcNode*p;p=G.vertices[v].firstarc;if(p){returnp->adjvex;}elseret

8、urnERROR;}StatusNextAdjVex(ALGraphG,intv,intw){ArcNode