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

实验报告
课程名称数据结构实验
实验项目实现深度优先搜索与广度优先搜索算法
专业班级计算机科学与技术1班姓名全永春学号 2011314103

指导教师成绩日期

一、目的与要求
1、通过本实验,掌握图,无向图的基本概念,掌握图的遍历。
2、掌握图的深度优先搜索(DFS)与广度优先搜索(BFS)算法。

二、实验内容
1、建立图的几种存储方式
2、图的深度优先搜索算法
3、图的广度优先搜索算法
三、实验原理
图的遍历是图的算法中一种非常重要的算法,通过建立图的存储结构,采用深度优先搜索与广度优先搜索算法可以进行图的遍历。广度优先遍历与深度优先遍历的区别在于:广度优先遍历是以层为顺序,将某一层上的所有节点都搜索到了之后才向下一层搜索;而深度优先遍历是将某一条枝桠上的所有节点都搜索到了之后,才转向搜索另一条枝桠上的所有节点。

四、实验步骤
。
,完成初始化图的工作。
(DFS)和广度优先搜索算法,可以采用菜单形式进行显示与选择。
(可以在键盘输入边的信息以构建一个无向图。以(a,b)的形式输入边的信息;对此无向图进行深度优先搜索,并输出正确的序列。)

#include<>
#include<>
#define max 20
typedef int Date ;
typedef char Info ;
typedef struct bian//边的数据结构
{
int zhi;
//Info info;
struct bian * N;
}bian;
typedef struct //节点数据结构
{
int i ;
bian *F;
}Vex;
typedef struct //用来作队列,栈
{
int top;
int button;
int a[100];
}S;
S s;
Vex v[max+1];//节点个数
bian *bu;
int n,e;
void create()//创建图
{ bian *b;
int i,v1,v2;
void memo();
printf("请输入节点个数N,边数E\n");
printf(" 节点个数N\n");
printf(" ");
scanf("%d",&n);
printf(" 边数E\n");
printf(" ");
scanf("%d",&e);
printf("请输入节点信息\n");
for(i=1;i<=n;i++)
{

scanf("%d",&v[i].i);

}
for(i=1;i<=n;i++)
v[i].F=0;
printf("请输入边\n");
printf(" 起点终点\n");
for(i=1;i<=e;i++)
{
printf(" ");
scanf("%d %d",&v1,&v2);

b=(bian *)malloc(sizeof(bian));
b->zhi=v2;
b->N=v[v1].F;
v[v1].F=b;
b=(bian *)malloc(sizeof(bian));
b->zhi=v1;
b->N=v[v2].F;
v[v2].F=b;

}
memo();
}
int p[max];
void vist(int i)
{

printf("%d ",v[i].i);
printf("-> ");

}
void aa()//查看表结构
{
void memo();
int i,j;bian* b;
printf(" num DAte next next next ....\n ");
for(i=1;i<=n;i++)
{
printf(" %d ",i);

printf("%d ",v[i].i);
b=v[i].F;
while(b!=0)
{
j=b->zhi;
printf("%d ",v[j].i);
b=b->N;
}
printf("\n");
}
printf("\n");
memo();
}
int f(int i)//返回没有被访问过的I的节点
{
int j=0;
bu=v[i].F;
while(bu!=0)
{

if(p[bu->zhi]==0)
{j=bu->zhi;br