图的广度遍历课程设计报告

《图的广度遍历课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录1.需求分析11.1问题描述11.2系统功能12.概要设计22.1流程图22.2结构体、函数及说明33.详细设计43.1遍历函数设计43.2容错性方法设计43.3生成邻接表设计53.4邻接表遍历设计64.程序源代码75.调试分析和测试结果165.1调试分析165.1调试案例165.3测试过程、结果截图：175.3.1容错性测试：175.3.2无向图（案例一）测试：205.3.3有向图（案例二）测试：226.课程设计总结24参考文献25241.需求分析1.1问题描述（1）对任意给定的图（顶点数和边数自定

2、），建立它的邻接表并输出。（2）然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索遍历。（3）画出搜索顺序示意图。1.2系统功能（1）首先输入图的类型，有向或无向图（因为遍历与权值无关，所以没有涉及带权图）。然后输入图的顶点数、边数和各条边，之后生成该图的邻接表并输出。（2）再输入要遍历该图的起点，然后从所输入的点广度搜索该图的邻接表，并按遍历顺序输出顶点内容。之后决定是否继续遍历该图或输入另一个需要遍历的图亦或是结束程序。242.概要设计2.1流程图开始输入图的类

3、型确定图的类型输入无向图输入有向图输入从哪个顶点开始遍历该图广度优先遍历该图是否从其他顶点开始重新遍历该图是否是否结束否是结束图2-1流程图242.2结构体、函数及说明typedefstructArcNode//邻接表表结点{intadjvex;//该弧所指向的顶点位置structArcNode*nextarc;//指向下一条弧的指针//InfoType*info;//该弧相关信息指针}ArcNode;typedefstructVNode//邻接表头结点{VertexTypedata;//结点信息ArcN

4、ode*firstarc;//指向第一条依附该结点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct//图{AdjListVertices;//邻接表头结点数组intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志(有向图:0,无向图:1)}ALGraph;voidprint(intv)//输出顶点信息intFirstAdjVex(ALGraphG,intu)//在邻接表G中取第u个头结点voidNextAdjVex(AL

5、GraphG,intu,intw)//在邻接表G中取第u个头结点之后的结点w的下一结点voidBFSTraverse(ALGraphG,queueQ,boolvisited[],intm,intn,void(*Visit)(int))//使用辅助队列Q从邻接表结点m开始n结束广度遍历邻接表图G243.详细设计3.1遍历函数设计voidBFSTraverse(ALGraphG,queueQ,boolvisited[],intm,intn,void(*Visit)(int))//使用辅助队

6、列Q从邻接表结点m开始n结束广度遍历邻接表图G{//按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。while(!Q.empty())Q.pop();//置空的辅助队列Qfor(intv=m;v

7、jVex(G,u);w>=0;w=NextAdjVex(G,u,w))//从以u为头结点的邻接表开始遍历到链表中的最后一个结点if(!visited[w])//w为u的尚未访问的邻接结点{visited[w]=true;Visit(w);//访问wQ.push(w);//w入队列}//if}//while}//if}//BFSTraverse*/3.2容错性方法设计cout<<"请输入图的弧数:";for(;;){gets_s(s);//以字符串形式接受所输入的数据t=atoi(s);//取出字符串中

8、的整型n=G.vexnum*(G.vexnum-1)/2;//计算整型合理范围24if(G.kind==1)n+=n;//修正整型合理范围if(t>n

9、

10、t<1)//如果整型不在合理范围内cout<<"错误!请输入一个大于0小于"<