数据结构与算法课程实验报告-图的应用.pdfVIP

数据结构与算法课程实验报告

实验4.图的应用

教学学期

课程编号

专业班级

学生学号

学生姓名

原创性声明

本人郑重声明：所呈交的《数据结构与算法课程实验报告》，是本人在任课教

师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本

文不含任何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重

要贡献的个人和集体，均已在文中以明确方式标明。若有不实之处，本人承担一切

相关责任。

学生签名：日期：年月日

（前面可加目录页）

一.实验目的

1.理解图的概念并熟悉有关术语。

2.熟练掌握邻接矩阵表示法和邻接表表示法。

3.掌握连通图遍历的基本思想和算法。

4.掌握最小生成树的有关概念和算法实现。

5.掌握最短路径有关概念和算法。

6.掌握拓扑排序的概念及实现。

二.实验内容

1.对给定的图，用邻接矩阵实现该图的深度优先搜索遍历。

2.对给定的图，用邻接矩阵实现该图的广度优先搜索遍历。

3.对给定的图，用邻接表实现该图的深度优先搜索遍历。

4.对给定的图，用邻接表实现该图的广度优先搜索遍历。

三.文献综述

数据结构（C语言版）习题解答及实训指导李根强、谢月娥

四.实验思路和技术路线（数据结构及算法）

（1，2）算法设计：首先定义图的类型为结构型，包含图中的顶点信息和邻

接矩阵两项信息，然后将输入边的信息建立邻接矩阵，再将深度搜索优先遍历和

广度优先搜索遍历写成子函数的形式，在主函数中调用他们；

（3，4）算法设计：首先定义图的邻接表数据类型，建立该图的邻接表，然

后再用子函数写出深度优先搜索遍历和广度优先搜索遍历的算法，在主函数中调

用它；

五.实验结果分析及心得

（1）对给定的图，用邻接矩阵实现该图的深度优先和广度优先搜索遍历：

1给定的图如下：

第1页

2广度优先和深度优先遍历程序如下：

#includestdio.h

#definen8//图中顶点数

#definee15//图中边数

#defineelemtypeint

intvisited[n+1];//访问标志数组，为false表示未访问，为true表

示已访问

structgraph//定义图的数据类型

{

elemtypev[n+1];//存放顶点信息v1,v2,...,vn,不使用v[0]存

储空间

intarcs[n+1][n+1];//邻接矩阵

}g;

voidcreatadj()//建立邻接矩阵

{

inti,j,k;

请输入%d个顶点信息

for(k=1;k=n;k++)

输入顶点信息

for(i=1;i=n;i++)

for(j=1;j=n;j++)

g.arcs[i][j]=0;

for(k=1;k=e;k++)

{

第2页

请输入第%d条边，共%d条边

输入一条边（i,j)

g.arcs[i][j]=