第二篇：图的实验报告 (1)

图的实验报告

1.实验题目

编写一个程序，用来建立图的邻接表存储并在此基础上实现图的深度优先遍历，广度优先遍历。

2.需求分析

本演示程序在C-Free环境下编写调试，完成图的邻接表存储图的深度和广度优先遍历。

（1）输入的形式和输入值得范围:执行图的构造函数时需要输入图的顶点数和边数以及每条边的关联定点编号。执行输出函数是要输入关联的顶点，执行main时输入深度和广度优先遍历的出发点。

在执行所有输入中，元素的值都是整数。

（2）输出形式：在所有操作中进行前都要显示要操作的内容，然后在显示执行结果。

（3）程序所能达到的功能：完成邻接表存储及深度优先遍历，广度优先遍历。

（4）测试数据：

（1）执行图的构造函数时输入8,9.

（2）执行输出函数时输入1,2  1,3  2,4  2,5  3,6  3,7  6,7  4,8  5,8.

（3）执行深度优先遍历时输入1

（4）执行广度优先遍历时输入1

3.概要设计

（1）为实现上述功能，需要定义图的数据结构。在邻接表的每个结点中有顶点域和链域组成。每个链表的上边附设表头结点。

表头结点                表结点

        

(2)本程序包含9个函数：

（1）主函数main（）。

（2）初始化队列函数initqueue（）

（3）队列判空函数quempty（）

（4）入队操作函数enqueue（）

（5）出对操作函数dequeue（）

（6）图的建立函数 creat_L（）

（7）图的输出函数output_L（）

（8）图的深度遍历函数dfsL（）

（9）图的广度遍历函数bfsL（）

4.详细设计

详见附件纸张

5.调试分析

Error（1）prototype declaration原因 void crear_L（Lgraph G）中L没有大写。

Error（2）null undeclared原因NULL没有大写

Error（3）structure has no member named ftont原因front拼写错误。

Error（4）conflicting types for’p’原因将q写成了p。

Error（5）G undeclared(first use in this function)原因函数声明是少些一个G

Warning(1)void类型有返回值了，改为int类型即可。

6.使用说明

程序名为graph.c，运行环境为DOS程序执行后有如下显示：

请输入图的顶点数和边数:

输入完成后会有如下显示：

请输入每条边的关联顶点编号:

执行成功后返回每条边的关联顶点后会有如下显示：

与[%d]关联的顶点有:

请输入深度优先遍历的出发点:

其中%d为每个关联顶点的数目

输入完成并执行成功后会返回遍历顺序且有如下显示：

请输入广度优先遍历的出发点:

输入完成得出结论

7.测试结果

（1）建立图的邻接表

输入顶点数和边数（8,9）后再输入每条边的关联顶点编号（1,2）（1,3）（2,4）（2,5）（3,6）（3,7）（6,7）（4,8）（5,8）

（2）分别输出与[%d]关联的顶点,如与[1]关联的顶点有：  3   2

（3）深度优先遍历

输入深度优先遍历的出发点:1  输出结果为1->3->7->6->2->5->8->4->

(4)广度优先遍历

请输入广度优先遍历的出发点:1      输出结果为1->3->2->7->6->5->4->8->