python深度优先搜索

深度优先搜索（Depth First Search，DFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着树的深度遍历子节点，直到到达某个叶子节点为止，然后返回到前一个节点，继续遍历它的其他子节点。这个过程一直进行，直到所有的节点都被遍历完为止。

在Python中，可以使用递归函数来实现深度优先搜索。下面是一个例子：

def dfs(node, visited):
    visited[node] = True
    print(node)
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(neighbor, visited)

# 例子：使用深度优先搜索遍历无向图
graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3],
    3: [2]
}
visited = [False] * len(graph)

dfs(0, visited)

在上面的例子中，`dfs`函数接受两个参数：当前节点和一个布尔数组`visited`，用于记录节点是否已经被访问过。在函数内部，首先将当前节点标记为已访问，并打印它的值。然后遍历当前节点的所有邻居节点，并对未访问过的邻居节点递归调用`dfs`函数。

最后，我们定义了一个无向图`graph`和一个`visited`数组，初始化为所有节点都未访问过。我们从节点0开始遍历整个图，输出每个节点的值，直到所有节点都被访问过为止。

需要注意的是，DFS算法的时间复杂度为O(V+E)，其中V为节点数，E为边数。对于稀疏图（即E较小），DFS算法比较快；但对于稠密图（即E接近于V^2），DFS算法的效率会比较低。因此，在实际应用中需要根据不同的场景选择合适的算法。