C++基础算法————深度优先搜索(DFS)

一、DFS算法原理

（一）基本思想

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。它从一个起始节点开始，沿着一个方向尽可能深入地探索，直到无法继续为止，然后回溯到上一个节点，继续探索其他方向。这一过程可以用递归或栈结构来实现。

（二）算法流程

1. 选择起始节点：从图中的某个节点开始，将其标记为已访问。
2. 递归探索：访问当前节点的未访问邻接节点，并将其标记为已访问。然后对每个邻接节点重复此过程。
3. 回溯：如果当前节点的所有邻接节点都已访问过，或者无法继续深入，则回溯到上一个节点。
4. 重复步骤：继续探索其他未访问的分支，直到所有节点都被访问。

（三）递归与迭代实现

• 递归实现：递归实现是最直观的，通过函数调用自身来实现深度优先搜索。递归实现的代码简洁明了，但可能会遇到栈溢出的问题。