深度优先搜索
深度优先搜索（Depth-First Search，简称DFS）是一种在图或树中遍历所有节点的算法。DFS从根节点开始遍历，沿着一条路径走到底，直到到达叶子节点或无路可走，然后回溯到上一个节点，继续走其它的路径，直到遍历完所有的节点。
原理
对于树来说，DFS的原理很简单。从根节点开始遍历，先访问其左子树，再访问其右子树。递归执行此操作，直至遍历完整棵树。
对于图来说，DFS的原理也非常简单。从任意一个节点开始遍历，访问其相邻节点，并标记已访问过的节点。递归执行此操作，直至遍历完整张图。
DFS可以使用递归或栈来实现。使用递归实现DFS的代码简单而直观，但可能出现栈溢出的风险。使用栈实现DFS虽然需要手动维护栈，但可以避免栈溢出的风险。
代码实现
递归实现
对于树来说，递归实现DFS非常简单。
def dfs_recursive(node): if node: dfs_recursive(node.left) dfs_recursive(node.right)
对于图来说，递归实现DFS同样非常简单。
visited = set() def dfs_recursive(graph, start): visited.add(start) for neighbor in graph[start]: if neighbor not in visited: dfs_recursive(graph, neighbor)
栈实现
对于树来说，栈实现DFS可以使用先序遍历或后序遍历的方式。下面是先序遍历的实现方式。
def dfs_stack(node): if not node: return stack = [node] while stack: node = stack.pop() print(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left)
对于图来说，栈实现DFS也非常简单。
def dfs_stack(graph, start): visited = set() stack = [start] while stack: node = stack.pop() if node not in visited: visited.add(node) stack.extend(graph[node] - visited) return visited
应用场景
DFS可以用于以下场景：
- 查找图或树中的所有节点。
- 判断图或树是否联通，即遍历整张图或树，判断所有节点是否被访问过。
- 求解图或树中的最短路径或最优路径（需要结合剪枝等优化技巧）。
总结
DFS是一种简单而常见的遍历算法，在很多场景下都有广泛的应用。由于DFS有栈溢出的风险，可以使用栈来实现DFS。同时，DFS在解决某些问题时可能会出现无解或者超时的情况，需要结合剪枝等优化技巧。
