实现深度优先搜索和广度优先搜索算法

佛山科学技术学院实验报告课程名称数据结构实验项目实现深度优先搜索与广度优先搜索算法专业班级10网络工程2姓名蒲永毅学号2010394223指导教师成绩日期2011年11月19日一、实验目的1、通过本实验，掌握图，无向图的基本概念，掌握图的遍历；2、掌握图的深度优先搜索（DFS）与广度优先搜索（BFS）算法。二、实验内容1、建立图的存储方式；2、图的深度优先搜索算法;3、图的广度优先搜索算法。三、实验原理图的遍历是图的算法中一种非常重要的算法，通过建立图的存储结构，采用深度优先搜索与广度优先搜索算法可以进行图的遍历；深度优先遍历是树的先根遍历的推广，是将某一条枝上的所有节点都搜索到了之后，才转向搜索另一条枝上的所有节点；广度优先遍历与深度优先遍历的区别在于：广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索。四、实验步骤建立图的存储结构；输入图的基本接点与信息，初始化图；编写图的深度优先搜索（DFS）和广度优先搜索算法（BFS）程序；采用菜单形式进行显示与选择。测试数据和结果显示（1）从键盘输入顶点数和边数；（2）输入顶点信息；（3）输入边的信息，以（a,b）的形式输入边的信息，构建一个无向图；（4）对此无向图进行深度优先搜索和广度优先搜索，并输出正确的序列。五、程序源代码及注释/********************************采用邻接表的存储结构*构建无向图*图的创建过程中暂不支持重复验证，因此不能对一条边进行重复定义******************************/#include<stdio.h>#include<malloc.h>#include<windows.h>#defineMAX_VERTEX_NUM20typedefstructArcNode(intadjvex;structArcNode*nextarc;//InfoType*info;}ArcNode;/**********************************链表结点的结构用于创建栈或是队列********************************/typedefstructLinkNode(ArcNode*parc;//存储指针地址structLinkNode*next;//指向一下个结点}LinkNode;typedefstructVNode(charcData;//顶点元素值ArcNode*firstarc;//指向第一条依附于该点的边}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct(AdjListvertices;intvexnum;//图的当前顶点数和弧数intarcnum;}ALGraph;intVisited[MAX_VERTEX_NUM];/**********************************将生成的图打印出来以便确认正确性********************************/intPrintCheck(ALGraph*pag)(inti;ArcNode*p;printf("\nChecktheGraph!\n〃)；printf("No\tdata\tnext\tnext\t\n");for(i=0;i<pag->vexnum;i++)(printf(〃％d\t%c\t〃，i,pag->vertices[i].cData);p=pag->vertices[i].firstarc;while(p)(printf("%d\t",p->adjvex);p=p->nextarc;}printf("\n");}return1;}/***************************采用前插法创建邻接表*************************/intCreateGraph(ALGraph*pag,intstart,intend)(ArcNode*arcNodes=(ArcNode*)malloc(sizeof(ArcNode));ArcNode*arcNodee=(ArcNode*)malloc(sizeof(ArcNode));ArcNode*p;if(!arcNodes||!arcNodee)return0;//从start->end生成关系arcNodes->adjvex=end;〃下一结点的位置p=pag->vertices[start].firstarc;if(!p)//第一个结点单独构造(arcNodes->nextarc=pag->vertices[start].firstarc;pag->vertices[start].firstarc=arcNodes;}else(while(p->nextarc)p=p->nextarc;p->nextarc=arcNodes;arcNodes->nextarc=NULL;}//end->start的关系生成arcNodee->adjvex=start;〃下一结点的位置p=pag->vertices[end].firstarc;if(!p)//第一个结点单独构造(arcNodee->nextarc=pag->vertices[end].firstarc;pag->vertices[end].firstarc=arcNodee;}else(while(p->nextarc)p=p->nextarc;p->nextarc=arcNodee;arcNodee->nextarc=NULL;}return1;}/*****************************************深度优先遍历,非递归方式*结点先访问再入栈*栈的存储结构直接采用了LinkNode构成的链表*采用前插法进行插入与删除，从而也可以完成栈的功能*栈空条件Stack->next==NULL***************************************/voidDFSTraverse(ALGraphag,intstart)(LinkNode*Stack=(LinkNode*)malloc(sizeof(LinkNode));//链表头结点，用做栈LinkNode*pStack=(LinkNode*)malloc(sizeof(LinkNode));//对栈操作的指针LinkNode*temp;〃临时存储ArcNode*p;inti;if(!pStack||!Stack)return;Stack->next=NULL;p=ag.vertices[start].firstarc;Visited[start]=1;//Flagprintf("\n输出深度优先遍历顺序:")；printf("%c〃,ag.vertices[start].cData);〃访问第一个点while(1)//正常情况下执行一次，为了打印孤立结点(//pushstackpStack->parc=p;pStack->next=Stack->next;//将？接入链式栈中Stack->next=pStack;//pushoverwhile(p&&(Stack->next))//当并且栈不为空时(while(p)(if(Visited[p->adjvex])p=p->nextarc;else(Visited[p->adjvex]=1;printf("%c〃，ag.vertices[p->adjvex].cData);//VisitFunction//pushstackpStack=(LinkNode*)malloc(sizeof(LinkNode));if(!pStack)return;〃结点建立不成功pStack->parc=p;pStack->next=Stack->next;Stack->next=pStack;//pushoverp=ag.vertices[p->adjvex].firstarc;}}//popstacktemp=Stack->next;Stack->next=temp->next;p=temp->parc->nextarc;free(temp);//popover}for(i=0;i<ag.vexnum;i++)//打印出孤立点(if(!Visited[i])printf("%c〃,ag.vertices[i].cData);p=ag.vertices[i].firstarc;}if(i=ag.vexnum)break;}printf("\n\n");};/*****************************************广度优先遍历,非递归方式*队列的存储结构直接采用了LinkNode构成的链表*采用后接法进行插入，并用前插法进行删除*从而完成队列的功能，队空条件Queue->next==NULL***************************************/voidBFSTraverse(ALGraphag,intstart)(LinkNode*Queue=(LinkNode*)malloc(sizeof(LinkNode));//链表头结点，用做队列LinkNode*pQueue=(LinkNode*)malloc(sizeof(LinkNode));//对队列操作的指针LinkNode*temp;//临时存储LinkNode*last;//指向最后一个元素的指针ArcNode*p;inti;if(!Queue||!pQueue)return;printf("\n输出广度优先遍历次序:")；printf("%c〃，ag.vertices[start].cData);p=ag.vertices[start].firstarc;Visited[start]=1;while(1)〃正常情况下执行一次循环(//EnQueuepQueue->parc=p;Queue->next=pQueue;pQueue->next=NULL;last=pQueue;//指向最后一个元素的指针//EnQueueoverwhile(p&&Queue->next)(while(p)(if(!Visited[p->adjvex])(Visited[p->adjvex]=1;printf("%c〃，ag.vertices[p->adjvex].cData);//VisitFunction//EnQueuepQueue=(LinkNode*)malloc(sizeof(LinkNode));if(!pQueue)return;pQueue->parc=p;pQueue->next=NULL;last->next=pQueue;last=last->next;//指向最后一个元素的指针//EnQueueover}p=p->nextarc;}//DeQueuetemp=Queue->next;p=ag.vertices[temp->parc->adjvex].firstarc;Queue->next=temp->next;//DeQueueover}for(i=0;i<ag.vexnum;i++)//打印出孤立点(if(!Visited[i])printf("%c〃,ag.vertices[i].cData);p=ag.vertices[i].firstarc;}if(i=ag.vexnum)break;}printf("\n\n");}/*******************************************主函数负责对图的初始化工作*其中包括图的结点初始化，边初始化*其中大部分的while(1)语句用于验证输入数据的有效性******************************************/voidmain()(ALGraphag;inti,n,m;intchoose;〃选择遍历结点intstart,end;〃边的起点与终点的位置printf("说明：采用邻接表的存储结构，生成无向图\n输入数据请回车确认\n\n");while(1)//结点个数有效性验证(printf(-请输入图的结点个数，并回车：〃)；scanf(〃%d〃,&n);if(n<MAX_VERTEX_NUM&&n>0)break;elseprintf("\n请注意结点个数不能大于20,并且不能为0!\n");}ag.vexnum=n;printf("\n初始化图的结点，输入字符并回车:\n");for(i=0;i<ag.vexnum;i++)//图的结点数据(printf("No.%d=",i);fflush(stdin);scanf(〃％c〃，&ag.vertices[i].cData);ag.vertices[i].firstarc=NULL;}m=(n-2)*(n+1)/2+1;〃顶点数为n的图最多的边的数量为mwhile(1)//边的数量有效性验证(printf(-请输入边的数量：〃)；fflush(stdin);scanf("%d",&i);if(i<=m&&i>=0)break;elseprintf("\n请注意边的数量不能大于%d,并且不能小于1!\n”,m);}ag.arcnum=i;printf("\n初始化图的边，结点从0开始计，最大为%d\n",n-1);for(i=1;i<=ag.arcnum;i++)(while(1)//起点有效性验证(printf("第<%d>条边的起点：〃，i);fflush(stdin);scanf("%d",&start);if(start<n&&start>=0)break;elseprintf("重新输入")；}while(1)〃终点有效性验证(printf("第<%d>条边的终点：〃，i);fflush(stdin);scanf("%d",&end);if(end<n&&end>=0&&end!二start)break;elseprintf("重新输入")；}printf(〃\n〃)；CreateGraph(&ag,start,end);}PrintCheck(&ag);〃打印出生成的图printf("\n开始进行图的遍历！\n");while(1)//起始点有效性验证(printf("请输入深度优先遍历的开始结点:");fflush(stdin);scanf("%d",&choose);if(choose>=0&&choose<n)break;elseprin