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

1、佛山科学技术学院实验报告课程名称数据结构实验项目实现深度优先搜索与广度优先搜索算法专业班级10网络工程2 姓名 蒲永毅 学号 2010394223指导教师 成绩 日期2011年11月19日一、实验目的1、通过本实验，掌握图，无向图的基本概念，掌握图的遍历；2、掌握图的深度优先搜索（DFS）与广度优先搜索（BFS）算法。二、实验内容1、建立图的存储方式；2、图的深度优先搜索算法;3、图的广度优先搜索算法。三、实验原理图的遍历是图的算法中一种非常重要的算法，通过建立图的存储结构，采用深度优先搜 索与广度优先搜索算法可以进行图的遍历；深度优先遍历是树的先根遍历的推广，是将某一条枝上的所有节点都搜索到

2、了之后，才 转向搜索另一条枝上的所有节点；广度优先遍历与深度优先遍历的区别在于：广度优先遍历是以层为顺序，将某一层上的 所有节点都搜索到了之后才向下一层搜索。四、实验步骤建立图的存储结构；输入图的基本接点与信息，初始化图；编写图的深度优先搜索（DFS）和广度优先搜索算法（BFS）程序；采用菜单形式进行显示与选择。测试数据和结果显示（1）从键盘输入顶点数和边数；（2）输入顶点信息；（3）输入边的信息，以（a,b）的形式输入边的信息，构建一个无向图；（4）对此无向图进行深度优先搜索和广度优先搜索，并输出正确的序列。五、程序源代码及注释/*采用邻接表的存储结构*构建无向图*图的创建过程中暂不支持重复

3、验证，因此不能对一条边进行重复定义 */ #include#include#include#define MAX_VERTEX_NUM 20typedef struct ArcNode(int adjvex;struct ArcNode* nextarc;/InfoType* info;ArcNode;/*链表结点的结构用于创建栈或是队列*/typedef struct LinkNode(ArcNode* parc;/存储指针地址struct LinkNode* next;/指向一下个结点LinkNode;typedef struct VNode(char cData;/顶点元素值ArcNod

4、e* firstarc;/指向第一条依附于该点的边VNode,AdjListMAX_VERTEX_NUM;typedef struct (AdjList vertices;int vexnum;图的当前顶点数和弧数int arcnum;ALGraph;int VisitedMAX_VERTEX_NUM;/*将生成的图打印出来以便确认正确性*/int PrintCheck(ALGraph* pag)(int i;ArcNode* p;printf(nCheck the Graph!n)；printf(Notdatatnexttnextt n);for(i=0; ivexnum; i+)(prin

5、tf(dt%ct，i,pag-verticesi.cData);p = pag-verticesi.firstarc;while(p)(printf(%dt,p-adjvex);p = p-nextarc;printf(n);return 1;*采用前插法创建邻接表*/int CreateGraph(ALGraph* pag,int start,int end)(ArcNode* arcNodes = (ArcNode*)malloc(sizeof(ArcNode);ArcNode* arcNodee = (ArcNode*)malloc(sizeof(ArcNode);ArcNode* p;

6、if(!arcNodes | !arcNodee) return 0;从start-end生成关系arcNodes-adjvex = end;/下一结点的位置p = pag-verticesstart.firstarc;if(!p) /第一个结点单独构造(arcNodes-nextarc = pag-verticesstart.firstarc;pag-verticesstart.firstarc = arcNodes;else(while(p-nextarc) p = p-nextarc;p-nextarc = arcNodes;arcNodes-nextarc = NULL;/end-st

7、art的关系生成arcNodee-adjvex = start;/下一结点的位置p = pag-verticesend.firstarc;if(!p) /第一个结点单独构造(arcNodee-nextarc = pag-verticesend.firstarc;pag-verticesend.firstarc = arcNodee;else(while(p-nextarc) p = p-nextarc;p-nextarc = arcNodee;arcNodee-nextarc = NULL;return 1;*深度优先遍历,非递归方式*结点先访问再入栈*栈的存储结构直接采用了 LinkNode

8、构成的链表*采用前插法进行插入与删除，从而也可以完成栈的功能*栈空条件 Stack-next = NULL*/void DFSTraverse(ALGraph ag,int start)(LinkNode* Stack = (LinkNode*)malloc(sizeof(LinkNode); /链表头结点，用做栈LinkNode* pStack = (LinkNode*)malloc(sizeof(LinkNode); /对栈操作的指针LinkNode* temp;临时存储ArcNode* p;int i;if(!pStack|!Stack) return;Stack-next = NULL

9、;p = ag.verticesstart.firstarc;Visitedstart=1; /Flagprintf(n输出深度优先遍历顺序：)；printf( %c ,ag.verticesstart.cData);/访问第一个点while(1)/正常情况下执行一次，为了打印孤立结点(/push stackpStack-parc = p;pStack-next = Stack-next;/将 p 接入链式栈中Stack-next = pStack;/push overwhile(p & (Stack-next) /当并且栈不为空时(while(p)(if(Visitedp-adjvex) p

10、 = p-nextarc;else(Visitedp-adjvex=1;printf( %c ，ag.verticesp-adjvex.cData); /Visit Function/push stackpStack = (LinkNode*)malloc(sizeof(LinkNode);if(!pStack) return; /结点建立不成功 pStack-parc = p;pStack-next = Stack-next;Stack-next = pStack;/push overp = ag.verticesp-adjvex.firstarc;/pop stacktemp = Stac

11、k-next;Stack-next = temp-next;p = temp-parc-nextarc;free(temp);/pop overfor(i=0; inext = NULL*/void BFSTraverse(ALGraph ag,int start)(LinkNode* Queue = (LinkNode*)malloc(sizeof(LinkNode); /链表头结点，用做队 列LinkNode* pQueue = (LinkNode*)malloc(sizeof(LinkNode); /对队列操作的指针LinkNode* temp;/临时存储LinkNode* last;/

12、指向最后一个元素的指针ArcNode* p;int i;if(!Queue | !pQueue) return;printf(n输出广度优先遍历次序:)；printf( %c ，ag.verticesstart.cData);p = ag.verticesstart.firstarc;Visitedstart = 1;while(1)正常情况下执行一次循环(/EnQueuepQueue-parc = p;Queue-next = pQueue;pQueue-next = NULL;last = pQueue;指向最后一个元素的指针/EnQueue overwhile(p & Queue-nex

13、t)(while(p)(if(!Visitedp-adjvex)(Visitedp-adjvex = 1;printf( %c ，ag.verticesp-adjvex.cData); /Visit Function/EnQueuepQueue = (LinkNode*)malloc(sizeof(LinkNode);if(!pQueue) return;pQueue-parc = p;pQueue-next = NULL;last-next = pQueue;last = last-next;/指向最后一个元素的指针/EnQueue overp = p-nextarc;/DeQueuetem

14、p = Queue-next;p = ag.verticestemp-parc-adjvex.firstarc;Queue -next = temp-next;/DeQueue overfor(i=0; iag.vexnum; i+)/打印出孤立点(if(!Visitedi) printf( %c ,ag.verticesi.cData);p = ag.verticesi.firstarc;if(i = ag.vexnum) break;printf(nn);*主函数负责对图的初始化工作*其中包括图的结点初始化，边初始化*其中大部分的while(1)语句用于验证输入数据的有效性*/void m

15、ain()(ALGraph ag;int i,n,m;int choose;选择遍历结点int start,end;边的起点与终点的位置printf(说明：采用邻接表的存储结构，生成无向图n输入数据请回车确认nn);while(1)/结点个数有效性验证(printf(请输入图的结点个数，并回车：)；scanf(%d,&n);if(n0) break;else printf(n请注意结点个数不能大于20,并且不能为0!n);ag.vexnum = n;printf(n初始化图的结点，输入字符并回车:n);for(i=0; iag.vexnum; i+)/图的结点数据(printf(No.%d =

16、 ,i);fflush(stdin);scanf(c，&ag.verticesi.cData);ag.verticesi.firstarc = NULL;m = (n-2)*(n+1)/2+1; 顶点数为n的图最多的边的数量为mwhile(1)/边的数量有效性验证(printf(-请输入边的数量：)；fflush(stdin);scanf(%d,&i);if(i=0) break;else printf(n请注意边的数量不能大于%d,并且不能小于1!n”,m); ag.arcnum = i;printf(n初始化图的边，结点从0开始计，最大为%dn,nT);for(i=1; i=ag.arcn

17、um; i+)(while(1)/起点有效性验证(printf(第条边的起点：，i);fflush(stdin);scanf(%d,&start);if(start=0) break;else printf(重新输入);while(1)/终点有效性验证(printf(第条边的终点：，i);fflush(stdin);scanf(%d,&end);break;if(end=0 & end!二start) else printf(重新输入);printf(n)；CreateGraph(&ag,start,end);PrintCheck(&ag); 打印出生成的图printf(n开始进行图的遍历！n);while(1)/起始点有效性验证(printf(请输入深度优先遍历的开始结点:);fflush(stdin);scanf(%d,&choose);if(choose=0 & choose=0 & choosen) break;else printf(重新输入);BFSTraverse(ag,choose); /广度优先遍历system(pause)；程序运行截图睛输入图的结点个数，并回车：4初始化图的结点，输入字符并回车: 国=a.No.l = bNd . 2 = cHo.3 = d请输入边的数量二4 初始化图的边，结点从0开始计最大为3 第*&的起点