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

数据结构 实验报告 实验名称 图的遍历 日期 2014-12-01 专业班级 计算机 中加 131班 地点 信息学院621 实验人 王鹏伟 学号 1座机电话号码3 同组人 单独完成 实验目的 按照老师要求实现图的深度和广度遍历； 学会图的深度和广度遍历的规则。 实验要求 任意给定一个图； 运用算法输出该图的深度和广度遍历结果。 三、实验内容 1、利用书本14.1 definitions以及上课老师PPT所讲的知识解决遍历问题，并输出结果。 四、实验过程和结果 部分实验代码： // 广度优先遍历实现BFS private void bfs // TODO Auto-generated method stub for int i 0; i vexnum; i++ visited[i] false; Queue q new LinkedList ; for int i 0; i vexnum; i++ if !visited[i] visited[i] true; visit i ; q.add i ; while !q.isEmpty int j Integer q.remove .intValue ; // 判断如果全部遍历完了就不需要循环了 if temp.size vexnum q.removeAll q ; return; for int k this.firstAdjVex j ; k 0; k this .nextAdjVex j, k if !visited[k] q.add k ; visited[k] true; visit k ; //深度优先遍历的实现DFS public void dfs for int i 0; i vexnum; i++ visited[i] false； Queue q new LinkedList ; for int i 0; i vexnum; i++ if !visited[i] visited[i] true; visit i ; q.add i ; while !q.isEmpty int j Integer q.remove .intValue ; // 判断如果全部遍历完了就不需要循环了 if temp.size vexnum q.removeAll q ; return; for int k this.firstAdjVex j ; k 0; k this .nextAdjVex j, k if !visited[k] q.add k ; visited[k] true; visit k ; 过程细节请调试源代码！ 实验结果： 广度优先遍历： 深度优先遍历： 实验总结 通过对图的遍历的处理，我初步认识了什么是图的广度优先和深度优先遍历，知道了如何用java 实现遍历算法。在解决图的优先遍历问题是最直接的方法就是把图画出来，深度遍历则从左子树做到最底，广度则横向最边。对于计算机编程中用到的算法考虑，则需要借助邻接矩阵或邻接表，深度则是在矩阵中尽可能的往纵向的找，广度则是尽可能的往横向的找。 虽然这个程序不是我自己写的，它是我从百度是有哪些信誉好的足球投注网站的，但是，通过我一点一点的看代码，分析代码，运行代码，我也算是搞懂了其中的思想。正如老师所说，当你不会的时候，就将在网上down下来的代码好好的多看几遍，不懂得地方据多问问，这也是一种学习方法。 数据库系统 实验报告 第2 页/ 共2页 第1 页/ 共2页 江 西 理 工 大 学