图的基本操作实验报告

1

《数据结构》

实 验 报 告 书

实验内容：图的基本操作 学院班级：计算机学院计算机科学与技术 姓 名：***

学 号：2011008****** 指导老师：高老师

2

前言

计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。

数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。

图的基本操作

实验目的

1、使学生可以巩固所学的有关图的基本知识。 2、熟练掌握图的存储结构。 3、熟练掌握图的两种遍历算法。

实验内容

[问题描述]

对给定图，实现图的深度优先遍历和广度优先遍历。 [基本要求]

以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用

3

户指定的结点为起点，分别输出每种遍历下的结点访问序列。 【测试数据】

由学生依据软件工程的测试技术自己确定。

实验前的准备工作

1、掌握图的相关概念。

2、掌握图的逻辑结构和存储结构。 3、掌握图的两种遍历算法的实现。

算法设计

图的深度优先：类似树的先根遍历，初始状态所有顶点未曾被访问，则深度优先从图中某个顶点v 出发，访问此顶点，然后依次从v 的未被访问的邻接点出发深度优先遍历图，直到图中所有和v 有路径相通的顶点都被访问到，若此图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点重复上述过程直到所有的顶点都被访问。

广度优先优先：从图中某顶点v 出发，在访问了v 之后依次访问v 的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使先被访问的顶点的邻接点选于后被访问的顶点的邻接眯被访问，直到图中所有已被访问的顶点的邻接点都被访问，若此图中尚有顶点未被访问，则另选图中一相未曾被访问的顶点作起始点重复上述过程。 因此定义一个数组存放顶点的值、定义个visited[] 来标志是否被访问。首先建立图，依次输入图的顶点数，图的顶点值，图的弧的条数，各每条弧所连接的两个顶点然后自动调用dfs()和bfs()两个函数把遍历的值输出来。

深度优先算法：dfs()

:寻找v 的还没有访问过的邻接点，循环找到v 的所有的邻接点，每找到一个都以该邻接点为新的起点递归调用深度优先算法，找下一个邻接点。 voiddfs(vexsb,adjmata,intv,int visited[],int n) {int w;

cout

while(w

if(visited[w]==0 && a[v][w]!=0) dfs(b,a,w,visited,n); w++; } }

广度优先算法：bfs()

：设置一个队列，并设置一个变量w 存放下一个邻接点的变量序号和队尾队首的指针。 voidbfs(vexsb,adjmata,intv,int visited[],int n) {

int queue[Max]; intw,rear,first;

rear=first=0; cout

queue[rear]=v; while(first!=rear){ first++;

v=queue[first]; w=0; while(w

if(a[v][w]==1 && visited[w]==0){ cout

查找v 在图中位置函数：locatevex()

：输入每第弧所连接的两条边时要定们v 在图中的位置。 intlocatevex(vexsb,charv,int n){ intk,i; k=-1;

for (i=0;i

4

主函数：main()

:定义了一些变量，输入输出等操作，以及深度优先，广度优先遍历时for 循环判断等。 void main(){ int n,m,i,j,k1,k2; vexs b; adjmat a; char v1,v2;

int visited[Max]; cout>n;

for (i=0;i

a[i][j]=0; //邻接矩阵赋初值

cout

for(i=0;i>b[i]; cout>m;

cout

cout>v1; cin>>v2;

k1=locatevex(b,v1,n);

k2=locatevex(b,v2,n); a[k1][k2]=1; a[k2][k1]=1; }

for(i=0;i

cout

for (i=0;i

if (!visited[i]) dfs(b,a,i,visited,n); cout

cout

if (!visited[i]) bfs(b,a,i,visited,n); cout

5

调试测试：

本测试采用书上第168页图7.13a 做为实验测试数据：

根据广度优先和深度优先推测结果分别：

设：V1=a、v2=b、v3=c、v4=d、v5=e、v6=f、v7=g、v8=h 广度优先：a->b->c->d->e->f->g->h 深度优先：

a->b->d->h->e->c->f->g

输入顶点数：

6

输入这8个顶点的值：分别为：V1=a、v2=b、v3=c、v4=d、v5=e、v6=f、v7=g、v8=h

输入弧的条数:9

依次输入每条弧所连接的顶点：

回车，直接调用深度优先算法和广度优先算法：

输出结果：

与预测值一样，实验成功。

总结：

通过本次实验，在同学和老师的指导下重新认识到了图的基本的操作：图的建立，图的遍历，以及加深了两种遍历算法的理解，加深了我对图的认识和理解。同时提高了我的西编程能力逻辑思维能力，动手能力等。

符：源代码：

#include #include #include using namespace std; #define Max 10

typedef char vexs[Max];

typedefintadjmat[Max][Max];

voiddfs(vexsb,adjmata,intv,int visited[],int n)

{

int w;

cout

while(w

7

w++;

while(w

if(visited[w]==0 && a[v][w]!=0) dfs(b,a,w,visited,n); w++; } }

voidbfs(vexsb,adjmata,intv,int visited[],int n) {

int queue[Max]; intw,rear,first; rear=first=0; cout

queue[rear]=v; while(first!=rear){ first++; v=queue[first]; w=0;

while(w

if(a[v][w]==1 && visited[w]==0){ cout

visited[w]=1; rear++; queue[rear]=w; } w++; } } }

intlocatevex(vexsb,charv,int n){ intk,i;

k=-1;

for (i=0;i

if (b[i]==v)

k=i;

return k; }

void main(){ int n,m,i,j,k1,k2; vexs b; adjmat a; char v1,v2;

int visited[Max]; cout>n;

for (i=0;i

a[i][j]=0;

cout>b[i]; cout>m;

cout

cout>v1;

cin>>v2;

k1=locatevex(b,v1,n); k2=locatevex(b,v2,n); a[k1][k2]=1; a[k2][k1]=1; } for(i=0;i

cout

for(i=0;i

if (!visited[i])

bfs(b,a,i,visited,n); cout

图的基本操作

8

";