佛山科学技术学院 实 验 报 告 课程名称 数据结构 实验项目 实现深度优先搜索与广度优先搜索算法 专业班级 10 网络工程2 姓 名 蒲永毅 学 号 2010394223 指导教师 成 绩 日 期 2011 年11 月19 日 一、实验目的 1、通过本实验，掌握图，无向图的基本概念，掌握图的遍历； 2、掌握图的深度优先搜索（DFS）与广度优先搜索（BFS）算法。 二、实验内容 1、建立图的存储方式； 2、图的深度优先搜索算法； 3、图的广度优先搜索算法。 三、实验原理 图的遍历是图的算法中一种非常重要的算法，通过建立图的存储结构，采用深度优先搜索与广度优先搜索算法可以进行图的遍历； 深度优先遍历是树的先根遍历的推广，是将某一条枝上的所有节点都搜索到了之后，才转向搜索另一条枝上的所有节点； 广度优先遍历与深度优先遍历的区别在于：广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索。 四、实验步骤 1．建立图的存储结构； 2．输入图的基本接点与信息，初始化图； 3．编写图的深度优先搜索（DFS）和广度优先搜索算法（BFS）程序； 4.采用菜单形式进行显示与选择。 5.测试数据和结果显示 （1）从键盘输入顶点数和边数； （2）输入顶点信息； （3）输入边的信息，以（a,b）的形式输入边的信息，构建一个 无向图； （4）对 此 无向图进行深度优先搜索和广度优先搜索，并 输出 正 确 的序列 。 五 、程序源 代 码 及 注 释 /******************************* *采用邻 接表 的存储结构 *构建无向图 *图的创 建过程中暂 不 支 持 重复 验证 ， 因此不能对一条边进行重复定义 ******************************/ #include #include #include #define MAX_VERTEX_NUM 20 typedef struct ArcNode{ int adjvex; struct ArcNode* nextarc; //InfoType* info; }ArcNode; /********************************* *链表结点的结构用于创建栈或是队列 ********************************/ typedef struct LinkNode{ ArcNode* parc; //存储指针地址 struct LinkNode* next; //指向一下个结点 }LinkNode; typedef struct VNode{ char cData; //顶点元素值 ArcNode* firstarc; //指向第一条依附于该点的边 }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum;...
