数据结构实验报告图的遍历

《数据结构实验报告图的遍历》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、HUNANUNIVERSITY课程实习报告题目：图的遍历问题学生姓名：学生学号：专业班级：指导老师：完成日期：一、需求分析把互联网比喻成一个蜘蛛网，那么Spider就是在网上爬来爬去的蜘蛛。网络蜘蛛是通过网页的链接地址来寻找网页，从网站某一个页面（通常是首页）开始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。这样看来，网络蜘蛛就是一个爬行程序，一个

2、抓取网页的程序。在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先。二、概要设计抽象数据类型以邻接表的形式存储图的数据，也就是用将用户的数据存入链表中。算法的基本思想深度优先：采用回溯法的算法，运用递归的方法，以深度优先为原则对图进行遍历。广度优先：采用队列的数据结构保存顶点，然后根据队列先进先出的原则对图进行广度优先遍历。程序的流程程序由三个模块构成：1、输入模块：将数据存入链表中，并初始化各数组的值，根据顶点和权值构建图。1、深度优先模块：将图以深度优先为原则开始遍历。2、广度优先模块：将图以广度优先为原则开始遍

3、历。三、详细设计算法的具体步骤先将用户的输入的顶点和边的数量，根据这些信息构建出图的结构，最后采取深度优先和广度优先的方法遍历该图。输入和输出的格式输入：首先输入顶点的数量，然后是各顶点对应的字母，再输入各条弧（权值都置为1）。输出：输出从首个顶点开始的广度优先遍历序列和深度先遍历序列。五、测试结果