实验三实现深度优先搜索与广度优先搜索算法.docx

（规格为A4纸或A3纸折叠）

实验目的；
通过本实验，掌握图、无向图的基本概念，掌握图的遍历。
掌握图的深度优先搜索（DFS）与广度优先搜索（BFS）算法。

实验内容；
建立图的几种存储方式
图的深度优先搜索算法
图的广度优先搜索算法

三、实验原理；
图的遍历是图的算法中一种非常重要的算法，通过建立图的存储结构，采用深度优先搜索与广度优先搜索算法可以进行图的遍历。
深度优先遍历是树的先根遍历的推广，是将某一条枝上的所有节点都搜索到了之后，才转向搜索另一条枝上的所有节点。
广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索。

四、实验步骤；
1.调试下列程序“创建图的程序一”，掌握无向图的构造算法和实现方式。
2.在此程序的基础上，完成图的深度优先搜索（DFS）和广度优先搜索算法，并输出遍历结果。
3.可以采用菜单形式进行显示与选择；从键盘输入边的信息以构建一个无向图。以（a，b）的形式输入边的信息；对此无向图进行深度优先搜索和广度优先搜索，并输出正确序列。

五、程序源代码及注释

六、实验结果分析及实验体会

体会：认识到深度与广度优先搜索的区别，在开始编程前，我查找大量书籍以求取帮助。然后我们宿舍决定一齐努力编写，但是由于每个人的想法不同，有些想用邻接矩阵或用邻接表。造成了分成两派去编。在这过程中，我明白到编写方程是极需要耐心与团队精神，我以后会更加努力去学习这门课程。