电子信息工程学系实验报告 ——适用于计算机课程
课程名称： 数据结构
实验项目名称：
图的遍历操作 实验时间：
班级：计应102 姓名： 学号：
实验目的：
掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。
实验内容：
题目：设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。
要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS和BFS遍历。
测试数据：
０ １ ０ ０ ０
１ ０ ０ ０ １
０ １ ０ １ ０
１ ０ ０ ０ ０
０ ０ ０ １ ０
实验要求：
按要求编写实验程序，将实验程序调试运行，写出在各种图的遍历方法中，输入测试数据所得的结果，并提交实验报告，写出调试运行的分析和体会。
实验结果：
实验总结：
逻辑结构：邻接矩阵
Dfs遍历：利用了递归的方法，开始访问一个节点的邻接节点 再访问这个节点的邻接节点 然后再访问另外一个邻接节点、依次下去 得以访问所有的节点、
通过这次试验，熟悉了递归的使用、对图的遍历方式更加理解了、
BFS遍历：这里利用了队列这种数据结构，原理是先访问所有节点的全部邻接节点，再访问邻接节点的全部节点、这样一层层下去。
实验源代码
#include <iostream>
#include <queue>
#define N 5
using namespace std;
int vi[N];
void print(int i)
{
printf("%c ",i+'a');
}
void connect(int a[N][N],int start)
{
for(int i=0;i<N;++i)
{
if(vi[i]==0&&a[start][i]==1)
{
print(i);
vi[i]=1;
connect(a,i);
}
}
}
void DFS(int a[N][N],int start)
{
memset(vi,0,sizeof(vi));
connect(a,start);
for(int i=0;i<N;++i)
{
if(!vi[i])
print(i);
}
}
void BFS(int a[N][N],int start)
{
int d;
memset(vi,0,sizeof(vi));
queue<int> temp;
temp.push(start);
while(!temp.empty())
{
d=temp.front();
temp.pop();
print(d);
vi[d]=1;
for(int i=0;i<N;++i)
{
if(vi[i]==0&&a[d][i]==1)
temp.push(i);
}
}
for(int i=0;i<N;++i)
{
if(!vi[i])
print(i);
}
}
int main()
{
int a[N][N]={
0,1,0,0,0,
1,0,0,0,1,
0,1,0,1,0,
1,0,0,0,0,
0,0,0,1,0,
};
printf("DFS遍历:");
DFS(a,0);
printf("\n");
printf("BFS遍历:");
BFS(a,0);
printf("\n");
return 0;
}
第二篇：数据结构图实验报告
