数据结构实验报告--图

【数据结构实验报告--图】【一、实验目的】

本实验旨在掌握图的基本概念、存储结构以及相关操作，并通过实验加深对图的理解。

【二、实验环境】操作系统：Windows 10编程语言：C++

开发工具：Dev-C++ 5.11【三、实验内容】1.图的定义与基本概念

1.1 图的定义：有向图、无向图

1.2 图的基本概念：顶点、边、路径、路径长度2.图的存储结构 2.1 邻接矩阵表示法 2.2 邻接表表示法3.图的操作

3.1 图的创建

① 手动输入图的顶点和边 ② 从文件中读取图的顶点和边 3.2 图的遍历

① 深度优先遍历（DFS） ② 广度优先遍历（BFS） 3.3 图的最小树 ① Prim算法 ② Kruskal算法 3.4 图的最短路径 ① Dijkstra算法 ② Floyd算法4.实验结果分析 4.1 图的创建结果 4.2 图的遍历结果 4.3 图的最小树结果 4.4 图的最短路径结果

【四、实验步骤】

1.定义图的数据结构和相关操作的函数原型。2.实现图的存储结构和相关操作的函数实现。

3.开发主程序，包括菜单、用户输入、调用图操作函数等。4.运行程序，测试各个功能是否正常进行。5.根据运行结果分析，进行必要的调试和优化。【五、实验结果】1.图的创建结果：

●手动输入图的顶点和边： ●顶点数.10 ●边数.15

●从文件中读取图的顶点和边： ●顶点数.8 ●边数.122.图的遍历结果： ●深度优先遍历：

●遍历路径.1 -> 2 -> 4 -> 5 -> 3

●广度优先遍历：

●遍历路径.1 -> 2 -> 3 -> 4 -> 53.图的最小树结果： ●Prim算法：

●最小树顶点集合：{1, 2, 4, 5}

●最小树边集合：{(1, 2), (2, 4), (2, 5)} ●Kruskal算法：

●最小树边集合：{(1, 2), (2, 4), (2, 5)}4.图的最短路径结果： ●Dijkstra算法：

●从顶点1到其他顶点的最短路径长度： ●1 -> 2、2 ●1 -> 3、5 ●1 -> 4、4 ●1 -> 5、6 ●Floyd算法：

●图的最短路径邻接矩阵：

●0 2 5 4 6 ●2 0 3 1 3 ●5 3 0 5 4 ●4 1 5 0 2 ●6 3 4 2 0【附件】无

【法律名词及注释】

1.顶点：图中的一个节点，可以表示实体或事件。

2.边：连接图中两个顶点的线段，表示两个顶点间的关联关系。3.路径：由一系列边连接起来的顶点序列。

4.路径长度：路径上所有边的权值之和，即路径上的总代价。5.有向图：图中的边有方向，表示顶点之间的单向关系。6.无向图：图中的边无方向，表示顶点之间的双向关系。【全文结束】