实现深度优先搜索和广度优先搜索算法.doc

佛山科学技术学院
实验报告
课程名称数据结构
实验项目实现深度优先搜索与广度优先搜索算法
专业班级 10网络工程2 姓名蒲永毅学号 2010394223
指导教师成绩日期 2011年11月19日
一、实验目的
1、通过本实验,掌握图,无向图的基本概念,掌握图的遍历;
2、掌握图的深度优先搜索(DFS)与广度优先搜索(BFS)算法。
二、实验内容
1、建立图的存储方式;
2、图的深度优先搜索算法;
3、图的广度优先搜索算法。
 
三、实验原理
图的遍历是图的算法中一种非常重要的算法,通过建立图的存储结构,采用深度优先搜索与广度优先搜索算法可以进行图的遍历;
深度优先遍历是树的先根遍历的推广,是将某一条枝上的所有节点都搜索到了之后,才转向搜索另一条枝上的所有节点;
广度优先遍历与深度优先遍历的区别在于:广度优先遍历是以层为顺序,将某一层上的所有节点都搜索到了之后才向下一层搜索。
四、实验步骤
;
,初始化图;
(DFS)和广度优先搜索算法(BFS)程序;
。

(1)从键盘输入顶点数和边数;
(2)输入顶点信息;
(3)输入边的信息,以(a,b)的形式输入边的信息,构建一个无向图;
(4)对此无向图进行深度优先搜索和广度优先搜索,并输出正确的序列。
五、程序源代码及注释
/*******************************
*采用邻接表的存储结构
*构建无向图
*图的创建过程中暂不支持重复验证,
因此不能对一条边进行重复定义
******************************/
#include<>
#include<>
#include<>
#define MAX_VERTEX_NUM 20
typedef struct ode{
int adjvex;
struct ode* nextarc;
//InfoType* info;
}ode;
/*********************************
*链表结点的结构用于创建栈或是队列
********************************/
typedef struct LinkNode{
ode* parc; //存储指针地址
struct LinkNode* next; //指向一下个结点
}LinkNode;
typedef struct VNode{
char cData; //顶点元素值
ode* firstarc; //指向第一条依附于该点的边
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
int vexnum; //图的当前顶点数和弧数
int um;
}ALGraph;
int Visited[MAX_VERTEX_NUM];
/*********************************
*将生成的图打印出来以便确认正确性