实验三实验报告1

数据结构实验报告三的核心内容是关于图的存储结构和算法实现。实验主要涉及了图的两种基本存储方式：邻接矩阵和邻接表，并通过这些结构实现图的遍历和其他典型应用，如拓扑排序、关键路径求解和单源点最短路径。 1. **邻接矩阵**： - 邻接矩阵是一种二维数组，用于表示图中顶点之间的邻接关系。在无向图中，邻接矩阵是对称的，即对于任意两个顶点u和v，邻接矩阵中的元素gra[u][v]和gra[v][u]相等。在有向图中，gra[u][v]表示从顶点u到顶点v存在一条边。实验要求建立无向图和有向图的邻接矩阵，并计算顶点的度。在C++代码中，`GraphMatrix`类被用来实现邻接矩阵，包含一个二维数组gra来存储边的信息，以及成员变量point_num和edge_num分别记录顶点数量和边的数量。`InsertPoint`函数用于插入新节点并初始化邻接矩阵。 2. **邻接表**： - 邻接表是一种更节省空间的图存储方式，尤其适用于稀疏图。它为每个顶点维护一个链表，链表中的元素表示与该顶点相邻的所有其他顶点。实验中，`Graph`类模板使用邻接表来存储有向图，`Vertex`类表示每个顶点，包含顶点名m_vertexName和指向相邻顶点的链表padjEdge。`Graph`类则负责管理所有顶点的邻接表。 3. **图的基本操作**： - 建立图：通过输入数据，可以使用邻接矩阵或邻接表创建图。 - 遍历图：遍历图包括深度优先搜索(DFS)和广度优先搜索(BFS)，用于访问图中的所有顶点。 - 拓扑排序：AOV网（Activity On Vertex，顶点上的活动）的拓扑排序是将有向无环图(DAG)的顶点按没有前驱的顶点优先输出，保证了输出序列是拓扑有序的。 - 关键路径：AOE网（Activity On Edge，边上的活动）的关键路径是项目中最长的路径，决定了项目的最短完成时间。 - 单源点最短路径：Dijkstra算法用于求解图中从指定源点到其余所有顶点的最短路径。 4. **程序实现**： - 在实验中，首先定义了类模板，实现了邻接矩阵和邻接表的结构，然后编写了相应的函数方法来完成特定的操作，如插入顶点、输出图信息、拓扑排序、关键路径计算和Dijkstra算法。主函数调用这些方法来完成实验要求的功能。 通过这个实验，学生能够深入理解图的概念，熟练掌握图的存储结构和算法实现，并能运用这些知识解决实际问题。实验不仅锻炼了编程能力，也提升了对数据结构的理论理解和应用能力。