实验六-图报告 下载本文

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY

数据结构 实 验 报 告

实验项目 学生姓名 完成日期 指导教师 实验成绩 评阅教师

实验六 卢雄 实验类别 学生学号 2016-11-25 袁科 提高篇 201501147 评阅日期

实验六 图基本操作的编程实现

【实验目的】

图基本操作的编程实现 要求:

图基本操作的编程实现(2学时,验证型),掌握图的建立、遍历、插入、删除等基本操作的编程实现,存储结构可以在顺序结构、链接结构、联合使用多种结构等中任选,也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。

【实验性质】

验证性实验(学时数:2H)

【实验内容】

编程对图进行存储(邻接矩阵或邻接表都可以,由学生自由选择),之后可以询问任何两个结点之间是否有通路和路径数。

设计一个将图形转成邻接链表的程序。

设计一个深度优先搜索法来查找图形的程序。

设计一个广度优先搜索法来查找一个图形的程序。 鼓励开发出难度更高的程序。

【思考问题】

1. 图的定义和特性?

2. 图的主要存储结构是什么?是独立的某种还是多种数据结构的综合? 3. 图的主要遍历思路是哪些? 4. 举出图的应用范例?

【参考代码】(以下内容,学生任意选择一个完成即可)

【实验分析、说明过程】

一、系统功能模块图 1.显示菜单 void showmenu() 2.图的创建 Create_l_Graph(source,destination,no); void print_l_graph(Graph *head) 3. 输出邻接链表 主 函 数 4. 元素入队int Enqueue(int Vertex) 5.元素出队int Dequeue() 6.广度优先搜索void BFS(int Vertex)

二:流程图分析 显示菜单 Y Y choice=1?输入图的类别、顶点和边数 N 图的创建 Y 输出邻接链表数据 choice=2? N Y 图的广度优先遍历 choice=3? N Y choice=4? 退出程序 N 结束 输入有误,重新输入 开始