资源描述：
《采用邻接表实现图的DFS和BFS》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、#include"stdio.h"#include"stdlib.h"#defineMVNum30#defineQueueSize30#defineVexTypeinttypedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVexNode{VexTypedata;ArcNode*firstarc;}VexNode,AdjList[MVNum];typedefstruct{intvexnum,arcnum;AdjListvertices;}ALGraph;intLo
2、cateVex(ALGraph*G,VexTypev){inti;for(i=0;i<=G->vexnum;i++){if(G->vertices[i].data==v)returni;}return-1;}voidCreateGraph(ALGraph*G){inti,j,k;intv1,v2;ArcNode*p=NULL,*q=NULL;printf("请输入顶点数和边数(输入格式为:顶点数边数)：");scanf("%d%d",&G->vexnum,&G->arcnum);printf("请输入顶点信息(顶点以1为起始，每个顶点以回车作为结束):
3、");for(i=1;i<=G->vexnum;i++){scanf("%d",&G->vertices[i].data);G->vertices[i].firstarc=NULL;}printf("请输入边的信息(输入格式为:i,j)：");for(k=1;k<=G->arcnum;k++){scanf("%d,%d",&v1,&v2);i=LocateVex(G,v1);j=LocateVex(G,v2);p=(ArcNode*)malloc(sizeof(ArcNode));if(!p)exit(1);p->adjvex=j;p->nexta
4、rc=G->vertices[i].firstarc;G->vertices[i].firstarc=p;q=(ArcNode*)malloc(sizeof(ArcNode));if(!q)exit(1);q->adjvex=i;q->nextarc=G->vertices[j].firstarc;G->vertices[j].firstarc=q;}}voidPrintGraph(ALGraph*G){inti;ArcNode*p=NULL;for(i=1;i<=G->vexnum;i++){printf("%d",G->vertices[i].data
5、);p=(ArcNode*)malloc(sizeof(ArcNode));if(!p)exit(1);p=G->vertices[i].firstarc;while(p){printf("-->%d",p->adjvex);p=p->nextarc;}printf("");}}typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MVNum];//深度优先搜索voidDFS(ALGraph*G,inti){ArcNode*p;printf("visitdata:%d",G->vertices[i].dat
6、a);//访问顶点vivisited[i]=TRUE;//标记vi已访问p=G->vertices[i].firstarc;//取vi边表的头指针while(p){//依次搜索vi的邻接点vj，这里j=p->adjvexif(!visited[p->adjvex])//若vi尚未被访问DFS(G,p->adjvex);//则以Vj为出发点向纵深搜索p=p->nextarc;//找vi的下一邻接点}}voidDFSM(ALGraph*G){inti;for(i=1;i<=G->vexnum;i++)visited[i]=FALSE;for(i=1;i<=G-
7、>vexnum;i++)if(!visited[i])DFS(G,i);}//广度优先遍历typedefstruct{intfront;intrear;intcount;intdata[QueueSize];}CirQueue;voidInitQueue(CirQueue*Q){Q->front=Q->rear=0;Q->count=0;}intQueueEmpty(CirQueue*Q){returnQ->count=QueueSize;}intQueueFull(CirQueue*Q){returnQ->count==QueueSize;}voidEn
8、Queue(CirQueue*Q,intx){if(QueueFu
