递归实现深度优先图遍历：从邻接矩阵到邻接表

深度优先遍历（Depth-First Search, DFS）是一种在图或树等数据结构中搜索节点的算法，它从起始节点开始，尽可能深地探索分支，直到找到目标节点或者无法继续为止，然后回溯到未访问过的节点。在这里，题目要求将图的深度优先遍历算法写成递归的形式，这在计算机科学中是一个常见的技巧，用于解决许多图论问题。 首先，我们需要理解图的基本概念。图是由顶点（vertices）和边（edges）组成的集合，表示不同对象之间的关系。在给定的例子中，图由5个城市（顶点）和连接它们的航空路线（边）构成。常见的图表示方法有邻接矩阵和邻接表。 1. **邻接矩阵**：这是一种二维数组，用于表示顶点间是否有边相连。对于无向图，如果顶点i和j相连，则邻接矩阵的元素A[i][j]和A[j][i]都为1；对于有向图，只有从i到j的边时，A[i][j]为1，A[j][i]为0。邻接矩阵在空间效率上较高，但不适用于稀疏图，因为大部分位置都是空的。 2. **邻接表**：更节省空间，适用于稀疏图，它使用链表来存储每个顶点的邻接节点。每个顶点的邻接表包含指向与之相连的顶点的指针，使得查询速度快于邻接矩阵。邻接表在实际应用中更为常见，特别是当图中边的数量远大于顶点数量的平方时。 为了实现深度优先遍历的递归版本，我们可以定义一个递归函数，例如`DFS(vertex, visited)`，其中`vertex`是当前访问的顶点，`visited`是一个记录已访问过的顶点集合。函数的执行流程如下： - 基本情况：如果当前顶点已经在`visited`集合中，表示已经到达了树的最深部分，返回。 - 递归步骤： - 将当前顶点`vertex`添加到`visited`集合中。 - 遍历与`vertex`相连的所有未访问过的顶点`neighbor`。 - 对每个`neighbor`调用`DFS(neighbor, visited)`，继续深入搜索。 - 回溯：在遍历完所有邻居后，从`visited`中移除`vertex`，以便尝试其他路径。 在邻接表上实现递归DFS，主要通过遍历顶点的邻接列表，对于每个邻接顶点，检查是否已被访问，如果没有，则递归调用。这样，算法会沿着一条路径尽可能深地探索，直到无法再前进，然后回溯到未探索的节点。 深度优先遍历在图论中有广泛应用，包括寻找路径、连通性检查、拓扑排序等。将它转化为递归形式有助于理解其工作原理，同时也便于在代码中实现和优化。在实际编程中，递归DFS的实现可能会结合循环和栈数据结构，以确保在内存管理上更为高效。