dfs时间复杂度_DFS与BFS——理解简单搜索(中文伪代码+例题)

DFS算法是一种用于图遍历或树遍历的算法。其核心思想是从起点开始递归地深入每一个可能的分支，直到无法继续为止，然后回溯到上一个节点，继续尝试其他分支。

DFS算法有两种实现方式：递归实现和非递归实现（使用栈）。

递归实现的DFS算法伪代码：

DFS(node):
    if node is None:
        return
    visit(node)
    for child in node.children:
        DFS(child)

非递归实现的DFS算法伪代码：

DFS(node):
    stack = [node]
    while stack:
        node = stack.pop()
        if node.visited:
            continue
        visit(node)
        node.visited = True
        for child in node.children:
            stack.append(child)

其中，visit(node)表示对节点node进行操作，例如打印节点值、记录路径等。

DFS算法的时间复杂度为O(V+E)，其中V为节点数，E为边数。因为每个节点和每条边都只会被访问一次。

下面是一个例题，用DFS算法求解从起点到终点的路径（leetcode 79题）：

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

实现代码：

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not board[0]:
            return False
        m, n = len(board), len(board[0])
        visited = [[False] * n for _ in range(m)]
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def dfs(i, j, k):
            if k == len(word):
                return True
            if i < 0 or i >= m or j < 0 or j >= n or visited[i][j] or board[i][j] != word[k]:
                return False
            visited[i][j] = True
            for dx, dy in directions:
                if dfs(i+dx, j+dy, k+1):
                    return True
            visited[i][j] = False
            return False

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False

时间复杂度为O(m*n*3^k)，其中m、n为网格大小，k为单词长度。因为每个格子都有可能走，所以是O(m*n)，而每次调用dfs函数会向四个方向递归，每个方向都不能重复走，所以是3^k。