深度优先搜索DFS在图遍历中的应用

"本文主要介绍了图的深度优先搜索算法（DFS），并提供了具体的邻接矩阵实现示例。" 深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法，它按照“深入”图的分支进行探索，直到达到某一深度后才回溯。在图的DFS中，从一个起点开始，先访问该节点，然后递归地访问其未被访问过的邻接节点，以此类推，直到所有与起始节点有路径相连的节点都被访问到，然后再回溯到尚未完全访问的邻接节点，直至所有节点都被访问。 在图的存储表示中，通常有两种方式：邻接矩阵和邻接表。邻接矩阵是一个二维数组，其中的元素表示图中两个节点之间是否存在边。如果节点i和节点j之间有边，那么在矩阵的第i行第j列处的值为1，否则为0。邻接表则是为每个节点维护一个列表，列表中的元素是与其相邻的节点。 在给定的代码示例中，使用了邻接矩阵表示法来存储图。`g[100][100]` 初始化了一个邻接矩阵，`n` 表示图中顶点的数量。函数 `dfs(int k)` 代表从顶点 `k` 开始的深度优先搜索过程。首先，它打印出当前访问的节点 `k`，然后通过循环遍历 `k` 的邻接节点，判断是否有边连接且未被访问过。如果满足条件，就对邻接节点调用 `dfs()` 进行递归搜索。 DFS 的核心思想是递归，它适用于解决一些回溯问题，如走迷宫。在迷宫问题中，每个小方格可以看作图的一个节点，0 表示可通行，1 表示障碍。DFS 会尝试从入口节点开始，沿着可行路径向下探索，直到找到出口或者所有可能的路径都尝试过。在这个过程中，使用一个 `visited[]` 数组来记录已经访问过的节点，避免重复访问。 总结来说，深度优先搜索（DFS）是一种重要的图遍历算法，它利用递归的方式探索图的深层结构，适用于解决寻找路径、回溯等问题。在实际应用中，可以通过邻接矩阵或邻接表等数据结构来存储图，并结合DFS算法进行节点的访问和路径的查找。