数据结构实验报告(三)：实现深度优先搜索与广度优先搜索算法.doc

佛山科学技术学院 实 验 报 告课程名称 数据结构 实验项目 实现深度优先搜索与广度优先搜索算法 专业班级 10网络工程2 姓 名 张珂卿 学 号 2010394212 指导教师 成 绩 日 期 2011年11月16日 一、实验目的1、通过本实验，掌握图，无向图的基本概念，掌握图的遍历；2、掌握图的深度优先搜索（DFS）与广度优先搜索（BFS）算法。二、实验内容1、建立图的存储方式；2、图的深度优先搜索算法；3、图的广度优先搜索算法。三、实验原理图的遍历是图的算法中一种非常重要的算法，通过建立图的存储结构，采用深度优先搜索与广度优先搜索算法可以进行图的遍历；深度优先遍历是树的先根遍历的推广，是将某一条枝上的所有节点都搜索到了之后，才转向搜索另一条枝上的所有节点；广度优先遍历与深度优先遍历的区别在于：广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索。四、实验步骤1建立图的存储结构；2输入图的基本接点与信息，初始化图；3编写图的深度优先搜索（DFS）和广度优先搜索算法（BFS）程序；4.采用菜单形式进行显示与选择。5.测试数据和结果显示 （1）从键盘输入顶点数和边数； （2）输入顶点信息； （3）输入边的信息，以（a,b）的形式输入边的信息，构建一个无向图； （4）对此无向图进行深度优先搜索和广度优先搜索，并输出正确的序列。五、程序源代码及注释/*采用邻接表的存储结构*构建无向图*图的创建过程中暂不支持重复验证，因此不能对一条边进行重复定义*/#include#include#include#define MAX_VERTEX_NUM 20typedef struct ArcNodeint adjvex;struct ArcNode* nextarc;/InfoType* info;ArcNode;/*链表结点的结构用于创建栈或是队列*/typedef struct LinkNodeArcNode* parc;/存储指针地址struct LinkNode* next;/指向一下个结点LinkNode;typedef struct VNodechar cData; /顶点元素值ArcNode* 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+)printf(%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;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;elsewhile(p-nextarc)p = p-nextarc;p-nextarc = arcNodes;arcNodes-nextarc = NULL;/end-start 的关系生成arcNodee-adjvex = start;/下一结点的位置p = pag-verticesend.firstarc;if(!p)/第一个结点单独构造arcNodee-nextarc = pag-verticesend.firstarc;pag-verticesend.firstarc = arcNodee;elsewhile(p-nextarc)p = p-nextarc;p-nextarc = arcNodee;arcNodee-nextarc = NULL;return 1;/*深度优先遍历,非递归方式*结点先访问再入栈*栈的存储结构直接采用了LinkNode构成的链表*采用前插法进行插入与删除，从而也可以完成栈的功能*栈空条件 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;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 = p-nextarc;elseVisitedp-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 = Stack-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;/指向最后一个元素的指针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-next)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;/DeQueuetemp = 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 main()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 = ,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,n-1);for(i=1; i=ag.arcnum; 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);if(end=0 & end!=start)break;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);/