图数据结构上机实验

根据给定的信息，本次实验主要涉及的是图的数据结构及其在计算机科学中的应用，特别是通过邻接矩阵和邻接表两种不同的表示方法来实现图，并基于这两种表示方式完成图的深度优先搜索（Depth-First Search, DFS）和广度优先搜索（Breadth-First Search, BFS）。 ### 图的基本概念 在数据结构中，图是一种非线性数据结构，由一组顶点（或称为节点）和一组连接这些顶点的边组成。图可以用来模拟各种现实世界的关系网络，例如社交网络、交通网络等。 ### 邻接矩阵表示法 邻接矩阵是一种用于表示图的数据结构，它使用一个二维数组来表示图中的顶点之间的关系。对于一个包含n个顶点的图，它的邻接矩阵是一个n×n的矩阵，其中元素A[i][j]为1表示顶点i与顶点j之间有边相连，为0则表示没有直接相连。 #### 邻接矩阵的特点： - **空间复杂度**：对于一个含有n个顶点的图，邻接矩阵的空间复杂度是O(n^2)。 - **边的查询效率**：邻接矩阵适合于查询两个顶点间是否有边，时间复杂度为O(1)。 - **适合的场景**：适用于密集图（即边的数量接近顶点数量的平方）。 ### 邻接表表示法 邻接表是一种更为节省空间的表示图的方式，它使用链表来存储每个顶点的邻接顶点列表。每个顶点都对应着一个链表，链表中的每一个节点记录着与该顶点相邻的其他顶点的信息。 #### 邻接表的特点： - **空间复杂度**：对于一个含有n个顶点和e条边的图，邻接表的空间复杂度是O(n+e)。 - **边的查询效率**：查询两个顶点间是否有边的时间复杂度为O(d)，其中d是顶点的度数。 - **适合的场景**：适用于稀疏图（即边的数量远小于顶点数量的平方）。 ### 实验内容详解 #### 实验一：基于邻接表的图表示和实现 实验代码首先定义了一个邻接表的数据结构`struct glist`和`struct MGraph`，其中`struct MGraph`包含一个整型数组`v`表示顶点集合，一个指针数组`fhead`指向各个顶点的链表头结点。实验中实现了两个函数`CreateGraph`和`VisitGraph`，分别用于创建邻接表表示的图和对该图进行广度优先遍历。 - **创建图**：用户输入顶点数量后，程序会为每个顶点创建一个链表，并初始化为一个空链表。接着用户输入边的数量以及每条边连接的两个顶点，程序将按照输入的信息构建图的邻接表表示。 - **广度优先遍历**：采用队列数据结构实现广度优先遍历。从一个起始顶点出发，将其入队，然后不断地取出队首元素访问，并将其未被访问过的邻接顶点依次入队，直到队列为空。 #### 实验二：基于邻接矩阵的图表示和实现 实验代码同样定义了一个数据结构`struct MGraph`，但这次使用了二维数组`e`来表示图的邻接矩阵。同样地，实验实现了`CreateGraph`和`VisitGraph`两个函数，用于创建邻接矩阵表示的图并对其进行深度优先遍历。 - **创建图**：用户输入顶点数量后，程序读取每个顶点的值。接着用户输入边的数量以及每条边连接的两个顶点，程序将根据输入信息构建图的邻接矩阵表示。 - **深度优先遍历**：采用递归方式实现深度优先遍历。从一个起始顶点出发，访问该顶点，然后依次访问与其相邻且未被访问过的顶点，访问完一个顶点后回溯到上一个顶点继续访问下一个邻接顶点，直至所有顶点都被访问。 通过这两个实验，学生不仅能够深入理解图的基本概念，还能够掌握图的不同表示方法以及如何利用这些表示方法实现图的遍历算法。这对于理解和解决实际问题中的图论问题具有重要意义。