图的深度和广度优先搜索遍历

《图的深度和广度优先搜索遍历》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、吉林工业职业技术学院（数据结构实训报告）（2012~2013学年第1学期）实训地点:软件开发实训室指导教师:赵秀艳、刘文宏专业班级:计算机3111学生姓名:36号折春雨2012年12月13日目录实训项目1实训目的1设计分析1设计方案2详细设计4运行调试12实训心得15参考文献16数据结构实训报告实训项目1.个人项目：图的深度和广度优先搜索遍历问题描述：给定一个无向图，利用邻接矩阵或邻接表进行存储，然后按照深度和广度进行遍历。要求：以吉林省的城市：白城、松原、长春、公主岭、四平、辽源、吉林市、通化、白山、延吉所构成的地理图为无向图。求以吉林市为出发点深度和广度优先搜索

2、遍历序列。2.小组项目：学生成绩管理系统问题描述：编写一个学生成绩管理系统，实现计算每个学生的总分、平均分，班级的总分、平均分，按分数高低排序。包含插入、删除、修改、查询、显示模块。要求：成绩包括本学期所开设的课程（数据结构、计算机网络、数据库原理、……），采用菜单程序编写。包含插入、删除、修改、查询、显示模块。实训目的通过本次实训，能够进一步巩固、掌握程序设计基础和数据结构课程的基本知识、基本技能。运用算法分析与程序设计的一般方法进行实际项目的开发。本项目需要具备熟练的数组和线性表知识，具备程序编写、调试的基本能力，具有一定的文字表达和报告撰写能力，具备办公软件使

3、用能力。设计分析1.个人项目：图的深度和广度优先搜索遍历图示一种较线性表和树更复杂的结构，在无向图图的结构中，节点之间的关系可以使任意的，无向图是指任意两个定点之间的连线时没有方向的，图中两个数据元素之间都可以相关。所以，首先选择适合的存储结构完成图的建立，我们采用栈来存储。其次是建立图的邻接矩阵存储，邻接矩阵表示法也称为数组表示法，就是用一位数组存储途中的定点信息。最后，完成图的深度和广度优先遍历。深度优先遍历就是从某个顶点出发，沿着它的一条路径不断深入地访问图上的顶点，并按访问的次序输出所有顶点。广度优先遍历类似于图的按层次遍历的过程。然后输出遍历序列。2.小组

4、项目：学生成绩管理系统学生成绩管理系统主要功能是对学生信息进行加工和处理，根据任务要求，系统要完成学生信息的采集，信息的维护，信息查询和报表输出等操作，因此可将系统的开发过程分为系统设计，学生数据结构设计，设计系统框架，学生数据的存储与重用，系统维护设计，数据查询，数据统计，报表输出八个任务。首先确定要处理的对象并对其进行描述，即画出数据结构列表，班级学生成绩管理系统要处理的对象是学生。然后按照系统功能的总体要求进行程序编制。整个系统还需要具有以下功能：维护功能，查询功能，统计功能，报表输出功能，存储和重用功能。设计方案1.个人项目：图的深度和广度优先搜索遍历把问题

5、分成三个部分：一是建立无向图，运用栈来建立；二是将无向图进行邻接矩阵存储；三是将图进行深度和广度优先遍历。实现第一个算法思想：建立一个队列，将无向图的节点数和边数输入，再将节点的内容和边指针输入，建立无向图。实现第二个算法思想：将建立好的无向图进行邻接矩阵存储，即矩阵的形式。实现第三个算法思想：无向图的深度优先遍历是选定任意一个节点作为起点，依次遍历和此节点有联系的节点，直至最后没有在与此节点有联系的节点为止。如果图中还有未被访问的节点，则选定任意未被遍历的节点作为起始点，直至图中所有节点都被遍历。无向图的广度优先遍历类似于二叉树的按层次遍历。假设从图中某定点V出发

6、，在访问了V之后一次访问V的哥哥未曾访问过的邻接点，然后分别从这些邻接点出发一次访问它们的邻接点，直至图中所有节点均被访问2.小组项目：学生成绩管理系统如图1所示学生管理系统录入学生成绩导入学生成绩查询学生成绩删除学生记录追加学生记录显示学生成绩统计学生成绩保存输入记录成绩进行排序退出个人总分和平均分单科平均分总分最高分总分最低分按学生学号排序按学生姓名排序按数据结构成绩进行排序按计算机成绩排序按数据库成绩排序图一学生成绩管理界面（1）建立一个明了的管理菜单。<1>录入学生成绩<2>导入学生成绩<3>查询学生成绩<4>删除学生记录、追加学生记录<5>显示学生记录<6

7、>统计学生成绩<7>保存输入记录<8>成绩进行排序<9>退出。（2）使操作人员很容易的完成对学生成绩的查询、修改、添加、保存和导入。（3）在统计与排序这一模块中又可分为多个可操作模块，大大增加了此系统的功能，如统计学生成绩中可分为按个人总分和平均分统计、按单科平均分统计、按总分最高分和总分最低分统计；而在排序这一模块中又分为按学生学号、学生姓名、学生各单科成绩排序，大大减少了工作量。（4）和以往系统不同，在它的模块中新增加拉保存与导入记录这两个模块，运用这两个模块可以将外界数据导入系统中或将本系统中的数据导入外界进行保存工作，以防数据丢失。（5）对要查询的数据要