图及其应用实验报告(C语言实现、键盘输入 有完整的源代码和两组实验数据)

### 图及其应用实验报告知识点梳理 #### 一、实验背景与目标 本次实验的主要目的是通过实践操作加深学生对图的基本概念、存储结构以及各种遍历方法的理解。具体来说，实验涵盖了以下几个方面： 1. **图的存储结构**：包括邻接矩阵和邻接表两种方式。 2. **图的遍历算法**：包括深度优先搜索(DFS)和广度优先搜索(BFS)。 3. **图的应用**：求解无向图中的关节点和求解图中最短路径。 #### 二、图的存储结构定义与创建 ##### 邻接矩阵 - **定义**：邻接矩阵是一种二维数组形式来表示图中顶点之间关系的方法。对于一个包含n个顶点的图，它的邻接矩阵是一个n×n的矩阵，其中元素A[i][j]表示第i个顶点到第j个顶点是否存在边或者边的权重。 - **适用场景**：适用于稠密图（即边的数量接近于顶点数量的平方）。 - **示例**：对于实验中的无向网g1，其邻接矩阵如下所示： - 0 5 8 7 0 3 - 5 0 4 0 0 0 - 8 4 0 5 0 9 - 7 0 5 0 5 6 - 0 0 0 5 0 1 - 3 0 9 6 1 0 ##### 邻接表 - **定义**：邻接表是另一种常用的图的存储结构，它通过链表的形式来存储图中各个顶点的邻居信息。 - **适用场景**：适用于稀疏图（即边的数量远小于顶点数量的平方）。 - **示例**：对于实验中的有向图g2和无向图g3，可以通过邻接表来表示各个顶点之间的连接关系。 #### 三、图的遍历 ##### 深度优先搜索(DFS) - **算法流程**： 1. 选择一个顶点作为起点进行访问，并标记为已访问。 2. 从这个顶点出发，递归地访问它的每一个尚未访问过的邻接顶点。 3. 当无法找到未访问的邻接顶点时，回溯至上一个顶点，继续查找未访问的邻接顶点。 - **应用场景**：适合探索所有可能的路径。 ##### 广度优先搜索(BFS) - **算法流程**： 1. 选择一个顶点作为起点进行访问，并标记为已访问。 2. 将该顶点的所有未访问的邻接顶点加入到队列中。 3. 从队列中取出一个顶点，重复上述过程，直到队列为空。 - **应用场景**：适合寻找最短路径等问题。 #### 四、图的应用 ##### 求无向连通图中的关节点 - **定义**：关节点是指删除后会导致图不再连通的顶点。 - **算法流程**：使用深度优先搜索(DFS)遍历图，并记录每个顶点的发现时间和低值(low value)。然后根据这些值来确定哪些顶点是关节点。 ##### 求最短路径 - **算法选择**：使用迪杰斯特拉(Dijkstra)算法来求解从一个指定的顶点到图中其他所有顶点的最短路径。 - **算法流程**： 1. 初始化：设置一个距离数组distance和一个标记数组visited，其中distance用来记录从起点到每个顶点的距离，而visited用来标记顶点是否已被访问。 2. 从未被访问且距离最小的顶点开始，更新距离数组。 3. 重复步骤2直到所有顶点都被访问过。 - **应用场景**：适用于计算图中两点之间的最短距离问题。 #### 五、源代码分析 实验中提供的源代码包含了多种图的操作和算法实现，如邻接矩阵的定义、DFS和BFS的实现等。通过阅读并理解这些代码，可以帮助学生更好地掌握图的相关知识和技术。 本次实验不仅涉及了图的基础理论知识，还包含了实际编程操作，旨在帮助学生全面理解图的概念、存储方式以及常见的算法应用。