Python 深度优先搜索算法|极客笔记

Python 深度优先搜索算法

什么是深度优先搜索算法

深度优先搜索算法（Depth First Search，简称DFS）是一种用于遍历或搜索树或图的算法。它从起始顶点开始，沿着树的深度访问子节点，并在访问完所有子节点之后才回溯到父节点。这种遍历方式类似于走迷宫时沿着一条路一直往前走，直到无法继续为止，然后返回前一个节点继续探索其他可能的路径。

深度优先搜索的特点

深度优先搜索算法具有以下特点：

递归调用：在深度优先搜索中，通常使用递归的方式来访问子节点，并在递归结束后返回上一层。
栈：可以使用栈来模拟递归调用的过程，将待访问的节点压入栈中，然后从栈中弹出节点进行访问。
深度优先：深度优先搜索以深度优先的方式遍历树或图的节点，即尽可能深地访问子节点。

递归实现深度优先搜索

下面是用Python编写的递归实现深度优先搜索的示例代码：

def dfs_recursive(node, visited):
    if node in visited:
        return
    visited.add(node)
    print(node)
    for neighbor in graph[node]:
        dfs_recursive(neighbor, visited)

# 定义一个邻接表表示图
graph = {
    1: [2, 3],
    2: [4],
    3: [5],
    4: [6],
    5: [],
    6: []
}

visited = set()
dfs_recursive(1, visited)

在上面的代码中，我们定义了一个深度优先搜索的函数dfs_recursive，它接受一个节点和一个已访问节点的集合作为参数。首先判断当前节点是否已经访问过，如果访问过则直接返回，否则将当前节点加入已访问集合中，并打印当前节点。然后遍历当前节点的所有相邻节点（根据邻接表graph中的定义），递归调用dfs_recursive函数访问相邻节点。

非递归实现深度优先搜索

除了递归方式，我们也可以使用栈来实现非递归的深度优先搜索算法。下面是用Python编写的非递归实现深度优先搜索的示例代码：

def dfs_iterative(start):
    stack = [start]
    visited = set()
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node)
            for neighbor in reversed(graph[node]):
                stack.append(neighbor)

# 定义一个邻接表表示图
graph = {
    1: [2, 3],
    2: [4],
    3: [5],
    4: [6],
    5: [],
    6: []
}

dfs_iterative(1)

在上面的代码中，我们定义了一个非递归实现深度优先搜索的函数dfs_iterative，它接受一个起始节点作为参数。我们使用栈stack来辅助遍历，首先将起始节点压入栈中，然后循环执行以下操作：从栈中弹出一个节点，如果该节点未被访问过，则将其加入已访问集合中，并打印该节点；然后遍历该节点的所有相邻节点，将相邻节点压入栈中，继续循环直到栈为空。