​​深度优先搜索（DFS）是解决图与树结构问题的经典算法，其核心思想是“一条路走到底”，通过递归或栈实现回溯，适用于全排列、连通性检测、迷宫求解等场景。​​ 以下通过两个经典例题解析DFS的应用逻辑与代码实现。

1. ​​全排列问题​​
   给定不重复字符串（如"abc"），输出所有可能的排列组合。DFS通过标记已选字符+回溯未选字符实现穷举：从第一个位置开始，依次选择未被标记的字符，递归至下一位置，完成排列后回溯状态。例如"abc"的输出为abc、acb、bac、bca、cab、cba。代码中需维护visited数组标记选择状态，递归边界为排列长度等于原字符串长度。

2. ​​八连通水坑计数​​
   在$N\times M$的网格中，相邻（包括对角）的'W'表示水域，求水坑数量。DFS从任意'W'出发，将其标记为'.'并向八个方向扩散搜索，每次遇到'W'则继续递归，直至连通区域全部标记完毕。水坑数即DFS的启动次数，时间复杂度为$O(NM)$。

3. ​​N皇后问题​​
   在$N\times N$棋盘放置皇后，要求同行、同列、对角无冲突。DFS逐行尝试放置皇后，通过列、对角线标记数组避免冲突，递归至最后一行即为合法解。回溯时需重置标记状态，复杂度为$O(N!)$。

​​提示​​：DFS的关键在于状态标记与回溯，合理剪枝可提升效率。实际应用中需注意堆栈溢出风险，大规模数据建议改用迭代实现或广度优先搜索（BFS）。