深度优先搜索

深度优先搜索

深度优先搜索（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)
1
2
3
4

对于图来说，递归实现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)
1
2
3
4
5
6
7

栈实现

对于树来说，栈实现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)
1
2
3
4
5
6
7
8
9
10
11

对于图来说，栈实现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
1
2
3
4
5
6
7
8
9

应用场景

DFS可以用于以下场景：

1. 查找图或树中的所有节点。
2. 判断图或树是否联通，即遍历整张图或树，判断所有节点是否被访问过。
3. 求解图或树中的最短路径或最优路径（需要结合剪枝等优化技巧）。

总结

DFS是一种简单而常见的遍历算法，在很多场景下都有广泛的应用。由于DFS有栈溢出的风险，可以使用栈来实现DFS。同时，DFS在解决某些问题时可能会出现无解或者超时的情况，需要结合剪枝等优化技巧。