树的广度优先遍历

《树的广度优先遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计说明书设计题目：数据结构课程设计专业：计算机科学与技术班级：2013级3班设计人：孟宪星山东科技大学2014年12月12日山东科技大学课程设计任务书　　　　计算机科学与技术专业2013级3班　　　　一、课程设计题目：　　　　　　　图的建立与广度优先遍历　　　　　　　　　　　　　　　　　二、设计原始资料：　　　　　　　　《程序设计语言》　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　《数据结构》　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　《C++面向对象的程序设计》　　　　

2、　　　　　　　　　　　　　　　　　　　三、设计应解决下列各主要问题：　　　　　　　　　　　　　　　　　　　　　　　　1图的邻接表表示：在第i行的单链表中，各结点（称作边结点）分别存放与同一个顶点vi关联的各条边。各条边配有标识dest，指示该边的另一个顶点（终顶点）；还配有指针link，指向同一链表中的下一条边地边结点（都与顶点vi相关联）。图的遍历:图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问,并且使图中的每个顶点仅被访问一次的

3、过设计说明书应附有下列图纸：开始输入图的类型确定图的类型输入无向图输入有向图输入从哪个顶点开始遍历该图广度优先遍历该图是否从其他顶点开始重新遍历该图是否是否结束否是结束五、命题发出日期：　　　　　　　　　　设计应完成日期：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　设计指导教师（签章）：　　　　　　　　　　　　　　　　　　　　　　　　系主任（签章）：　　　　　　　　指导教师对课程的评语　　　　　　指导教师（签章）：　　　　　　　　　　　　　　　　　　　　　　年　　月　　日山东科技大

4、学学生课程设计图的建立与广度优先遍历1、课程设计的目的课程设计是对学生的一种全面的综合训练，是与课堂听讲、自学、练习、上机实习相辅相成的教学环节。课程设计的题目通常比平时练习与上机实习复杂得多，也更接近实际。其目的是使学生深化理解和灵活掌握教学内容，并学会如何把书上学到的知识用于解决实际问题，培养软件工作所需的问题分析、软件设计、算法设计和实际动手编程、调试的能力。这个题目的课程设计是要掌握图的邻接矩阵的存储结构和图的广度优先遍历。2、问题分析和任务定义2.1问题描述：画出下图所示的无向图的邻接表，使得其中每个无项边结点中第一个顶点号小于第

5、二个顶点号，且每个顶点的各邻接边的链接顺序，，为它所邻接到的顶点序号由小到大的顺序。列出广度优先搜索遍历该图所得顶点序列和边的序列。125364山东科技大学学生课程设计2.2问题分析和任务定义图的邻接表表示：在第i行的单链表中，各结点（称作边结点）分别存放与同一个顶点vi关联的各条边。各条边配有标识dest，指示该边的另一个顶点（终顶点）；还配有指针link，指向同一链表中的下一条边地边结点（都与顶点vi相关联）。图的遍历:图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。图的遍历是从图中某个顶点出发，沿着

6、某条搜索路径对图中其余每个顶点进行访问,并且使图中的每个顶点仅被访问一次的过程。1、存储结构设计按无向图的邻接表存储山东科技大学学生课程设计1、主要程序设计4.1.广度优先遍历的定义在访问了起始点之后,首先依次访问起始点的各个邻接点,然后依次访问这些顶点中未被访问过的邻接点.依此类推,直到所有被访问到的顶点的邻接点都被访问过为止.4.2广度优先搜索的过程4.2.1算法基本思想：首先访问图中某一指定的出发点Vi；然后依次访问Vi的所有接点Vi1，Vi2…Vit；再次访问Vi1，Vi2…，Vit的邻接点中未经访问过的顶点，依此类推，直到图中所有

7、顶点均被访问为止。4.2.2具体过程：山东科技大学学生课程设计从广度优先搜索遍历方法可知，先被访问的顶点的邻接点也被访问，即假设顶点V在W之前被访问，那么顶点V的所有未经访问的邻接点也在顶点W的所有未经访问的邻接点之前被访问。这样可以在广度优先遍历的算法中设置一个队列结构，用以保存已访问过的顶点的序号，访问该顶点的所有未经访问的顶点。广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样会出现回退的现象。因此它不是个递归的过程。为了实现逐层访问，算法中使用了一个队列以记忆正在访问的这一层和上一层的顶点，以便于向

8、下一层访问。为了避免重复访问，需要一个辅助函数visitvex[]给被访问过的顶点加标记。4.3图的广度优先遍历流程图开始输入图的类型确定图的类型输入无向图输入有向图输入从哪个顶