资源描述：
《数据结构课程设计报告《图的遍历》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构课程设计报告班级：姓名：学号：16目录一，设计任务----------------------------------------3二、设计时间----------------------------------------3三、设计内容----------------------------------------31、需要分析----------------------------------------32、概要设计----------------------------------------33、详细设计-------
2、---------------------------------44、测试与分析--------------------------------------9四、设计总结-----------------------------------------10源程序清单--------------------------------------1116一．设计任务：我选课程设计是自选题目《图的遍历》。要求：设计一个程序，实现图的广度，深度优先遍历。二、设计时间2009年12月28日三、设计内容1、需求分析本题目需要解决的问题是将一幅已知图
3、，对图进行遍历，并完成：（1）输出它的邻接矩阵；（2）根据人工选择进行深度优先搜索（Depth_FirstSearch）和广度优先搜索（Breadth_FirstSearch），将搜索结果放入一队列中；（3）将队列中的搜索结果输出。2、概要设计：(1)抽象数据的类型定义数据对象：V是图具有相同特性的数据元素的集合，称为定顶点集数据关系：RR={VR}VR={/v,w∈v且p(v,w)}基本操作：CreateGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合操作结果：按V和VR的定义构造图G基本操作：DFS
4、Traverse(G,Visit())BFSTraverse(G,Visit())（2）主程序的流程以及各程序模块之间的调用关系：16CreateGraph算法打印邻接矩阵初始化成功选择如何遍历开 始深度优先遍历广度优先遍历结 束 NYDB3、详细设计：（1）定义图typedef struct{ intV[M]; intR[M][M]; intvexnum;}Graph;16（2）创建图voidcreatgraph(Graph*g,intn){ inti,j,r1,r2; g->vexnum=n; /*顶点用i表
5、示*/ for(i=1;i<=n;i++) { g->V[i]=i; } /*初始化R*/ for(i=1;i<=n;i++) for(j=1;j<=n;j++) { g->R[i][j]=0; } /*输入R*/ printf("PleaseinputR(0,0END):"); scanf("%d,%d",&r1,&r2); while(r1!=0&&r2!=0) { g->R[r1][r2]=1; g->R[r2][r1]=1; scanf("%d,%d",&r1,&r2); }}（3）全局
6、变量：访问标志数组voidprintgraph(Graph*g){inti,j;for(i=1;i<=g->vexnum;i++){for(j=1;j<=g->vexnum;j++) { printf("%2d",g->R[i][j]); } printf(""); }}（4）访问顶点intvisited[M];16voidvisitvex(Graph*g,intvex){printf("%d",g->V[vex]);}（5）获取第一个未被访问的邻接节点intfirstadjvex(Graph*g,intvex){in
7、tw,i;for(i=1;i<=g->vexnum;i++) { if(g->R[vex][i]==1&&visited[i]==0) { w=i; break; } else { w=0; } } returnw;}/*获取下一个未被访问的邻接节点(深度遍历)*/intnextadjvex(Graph*g,intvex,intw){ intt; t=firstadjvex(g,w); returnt;}（6）深度递归遍历 voiddfs(Graph*g,int vex) { int w
8、; visited[vex]=1; visitvex(g,vex); for(w=firstadjvex(g,vex);w>0;w=nextadjvex(g,vex,w)) if(!vi
