📢博客主页：https://blog.csdn.net/2301_
📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！
📢本文由 JohnKi 原创，首发于 CSDN🙉
📢未来很长，值得我们全力奔赴更美好的生活✨
深度优先搜索（DFS）是一种用于遍历或搜索树或图数据结构的算法。其核心原理是从起始顶点开始，沿着路径尽可能深地探索，直到无法继续前进时才回溯。
DFS 的工作方式类似于在迷宫中探索，一旦进入一个通道，就尽可能地沿着这个通道走到底，直到遇到死胡同或者已经没有未访问的分支，然后再回溯到上一个岔路口，尝试其他路径。形象地说，DFS 就像是一个勇敢的探险家，不断深入未知领域，只有在走投无路时才会回头寻找其他可能性。
在 C++ 中，DFS 可以通过递归或者显式栈来实现。例如，在解决迷宫问题时，我们可以用一个二维数组模拟平面，用一个数组记录坐标是否被访问过，然后从起点开始，使用 DFS 算法不断尝试向四个方向移动，直到找到终点或者遍历完所有可能的路径。
总之，DFS 是一种强大的算法，在 C++ 编程中有着广泛的应用，可以帮助我们解决各种复杂的问题。
在 C++ 中，使用递归实现 DFS 具有简洁易懂的特点。递归实现利用函数调用栈隐式地进行回溯，代码结构清晰，易于理解和实现。以图的遍历为例，递归函数接受当前节点、图的邻接表和访问标记数组为参数，首先标记当前节点为已访问，然后遍历当前节点的所有邻居节点。如果邻居节点尚未访问，则递归地进行深度优先搜索。这种方式使得代码逻辑直观，对于小型图或者树的遍历非常高效。
然而，在遍历大图时，递归实现可能会导致栈溢出问题。这是因为递归调用会在栈上分配空间，当递归深度过大时，栈空间可能会耗尽。例如，在处理非常深的树或者大规模的图时，递归实现可能会因为栈溢出而失败。据统计，在一些实际应用中，当图的节点数超过一定数量（如几万甚至更多）时，递归实现的 DFS 就有可能出现栈溢出问题。
使用栈进行迭代实现 DFS 可以避免在深度较大的图中出现栈溢出风险。迭代实现使用显式栈来模拟递归的过程，每次从栈中取出一个节点，访问其邻居，并将未访问的邻居压入栈。这种方式不依赖于函数调用栈，因此可以处理深度较大的图而不会出现栈溢出问题。
在迭代实现中，我们首先创建一个栈和一个访问标记数组。将起始节点压入栈中，并标记为已访问。然后，在循环中，不断从栈中取出节点进行访问。如果取出的节点尚未访问，则访问该节点，并将其邻居节点压入栈中。通过这种方式，我们可以确保图中的每个节点都被访问到。
与递归实现相比，迭代实现的代码较为冗长，但更加健壮。它可以处理大规模的图，并且可以更好地控制遍历的过程。例如，在处理复杂的图结构时，我们可以根据需要对栈的操作进行优化，以提高遍历的效率。
在迷宫问题中，DFS 可以用于寻找从起点到终点的路径。例如，在一个二维迷宫中，我们可以将迷宫看作一个图，每个格子是一个节点，相邻的格子之间有边连接。从起点开始，使用 DFS 不断尝试向四个方向移动，直到找到终点或者遍历完所有可能的路径。在这个过程中，我们可以记录下路径上的节点，以便在找到终点后回溯得到完整的路径。据实际测试，对于一个中等规模的迷宫（如 10x10 的迷宫），DFS 可以在较短的时间内找到路径。
在有向无环图中，DFS 可以用于拓扑排序。拓扑排序的目标是将图中的节点按照依赖关系进行排序，使得对于任意一条有向边 (u, v)，节点 u 在排序后的序列中出现在节点 v 之前。通过对图进行 DFS，并在回溯时将节点加入到排序结果中，可以得到一个满足拓扑顺序的序列。例如，在任务调度问题中，每个任务可能依赖于其他任务的完成，使用拓扑排序可以确定任务的执行顺序，确保所有任务能够按照正确的顺序完成。
在一些谜题和游戏中，DFS 也有广泛的应用。比如八皇后问题，要求在一个 8x8 的棋盘上放置 8 个皇后，使得它们不能相互攻击。可以使用 DFS 遍历所有可能的放置方案，找到满足条件的解。在这个过程中，每次尝试在一个位置放置皇后，如果放置后不满足条件，则回溯到上一步重新尝试。据统计，通过 DFS 可以在合理的时间内找到八皇后问题的所有 92 组解。
对于一个图，DFS 可以用于检测其连通性。从图中的任意一个节点开始进行 DFS，如果能够访问到图中的所有节点，则说明该图是连通的；否则，图是不连通的。例如，在网络拓扑结构中，我们可以使用 DFS 来检测网络中的节点是否都能够相互通信。如果网络是连通的，那么从任何一个节点发送的数据都可以到达其他所有节点；如果网络不连通，则需要采取相应的措施来确保数据的传输。
DFS 可以用于生成随机迷宫。一种常见的方法是从一个随机的起点开始，不断地随机选择一个未访问的相邻节点进行扩展，直到无法继续扩展为止。在这个过程中，我们可以记录下路径，从而生成一个迷宫。例如，使用 DFS 生成一个 10x10 的迷宫，通常可以在几毫秒内完成。生成的迷宫具有随机性和复杂性，可以用于游戏开发或者算法测试。
在解决迷宫问题时，我们可以使用 DFS 来寻找从起点到终点的路径。具体实现可以通过递归或者迭代的方式进行。以递归方式为例，我们从起点开始，检查当前位置的四个方向（上、下、左、右）是否可行。如果可行，则继续向该方向进行深度优先搜索，直到找到终点或者无法继续前进。在搜索过程中，我们可以使用一个二维数组来记录已经访问过的位置，以避免重复访问。同时，我们可以使用一个栈或者向量来保存探索过程中的坐标，以便在找到终点后回溯得到完整的路径。
例如，以下是使用递归方式解决迷宫问题的 C++ 代码示例：
这段代码中，dfs函数使用递归的方式在迷宫中进行深度优先搜索，找到从起点到终点的路径。如果找到了路径，则将路径中的坐标存储在path向量中，并在主函数中输出路径。如果没有找到路径，则输出 “No path found.”。
以最大岛屿面积问题为例，我们可以使用 DFS 在二维矩阵中解决这个问题。具体来说，我们从一个陆地格子开始，使用 DFS 遍历与其相邻的陆地格子，并记录遍历过的格子数量，即为该岛屿的面积。然后，我们继续遍历其他未被访问过的陆地格子，找到最大的岛屿面积。
以下是使用 DFS 解决最大岛屿面积问题的 C++ 代码示例：
在这段代码中，maxAreaOfIsland函数遍历二维矩阵，找到所有的陆地格子，并调用dfs函数计算每个岛屿的面积。dfs函数使用递归的方式遍历与当前格子相邻的陆地格子，并将其标记为已访问，最后返回岛屿的面积
另外，我们还可以使用方向数组的方式来实现 DFS，代码如下：
这种写法使用方向数组来处理上下左右的遍历，更加简洁和方便。
在求解朋友圈数量问题中，我们可以使用 DFS 来体现其在传递关系问题中的作用。例如，给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果 M [i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。我们可以使用 DFS 算法来计算所有学生中的已知的朋友圈总数。
以下是使用 DFS 解决朋友圈问题的 C++ 代码示例：
在这段代码中，findCircleNum函数遍历所有学生，如果当前学生未被访问，则调用dfs函数进行深度优先搜索，将与当前学生互为朋友的学生标记为已访问，并增加朋友圈数量。dfs函数使用递归的方式遍历与当前学生互为朋友的学生，并将其标记为已访问。
在大洋流水问题中，我们可以从大洋开始向上流，利用 DFS 确定能流到太平洋和大西洋的位置。具体来说，我们从太平洋和大西洋的边界开始，使用 DFS 遍历与其相邻的格子，如果格子的高度不小于当前格子的高度，则可以流向该格子。最后，我们遍历整个矩阵，找到既能流到太平洋又能流到大西洋的格子。
以下是使用 DFS 解决大洋流水问题的 C++ 代码示例：
在这段代码中，pacificAtlantic函数首先初始化两个布尔数组toPa和toAt，分别表示能够流到太平洋和大西洋的格子。然后，从太平洋和大西洋的边界开始，使用 DFS 遍历与其相邻的格子，并将能够流到相应海洋的格子标记为true。最后，遍历整个矩阵，找到既能流到太平洋又能流到大西洋的格子，并将其坐标加入结果列表中。DFS函数使用递归的方式遍历与当前格子相邻的格子，并将能够流到相应海洋的格子标记为true。
以下是使用递归方式遍历无向图的 C++ 代码示例：
在这段代码中，undigraph类表示无向图，其中DFS函数使用递归的方式遍历无向图中的节点，smallestadjvertex函数和nextadjvertex函数分别用于寻找当前节点的最小序号邻接顶点和下一个邻接顶点，DFStraverse函数用于遍历整个无向图。
在二叉树的遍历中，DFS 可以用于前序、中序和后序遍历。以下是使用递归方式实现二叉树的前序、中序和后序遍历的 C++ 代码示例：
在这段代码中，TreeNode结构体表示二叉树的节点，preOrderRecur函数、inOrderRecur函数和postOrderRecur函数分别用于实现二叉树的前序、中序和后序遍历。这些函数使用递归的方式遍历二叉树中的节点，并输出节点的值。
总之，DFS 在不同的数据结构中有着广泛的应用，可以帮助我们解决各种复杂的问题。
本篇博文对 深度优先搜索（DFS） 做了一个较为详细的介绍，不知道对你有没有帮助呢
觉得博主写得还不错的三连支持下吧！会继续努力的~
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/cjjbc/19725.html