python深度优先搜索函数

在Python中，深度优先搜索（Deep-First Search, DFS）是一种用于遍历或搜索树形数据结构（如图论中的图）的算法。它从根节点开始，尽可能深地探索每一条路径，直到到达叶子节点，然后回溯到上一级节点并尝试其他分支，直到所有的节点都被访问过。

下面是一个简单的例子，展示如何用Python编写一个通用的深度优先搜索函数：

def dfs(graph, start, visited=None):
    """
    graph: 图形的数据结构（如字典，邻接列表等）
    start: 起始节点
    visited (optional): 存储已访问节点的集合，默认为None
    """
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(f"Visiting node: {start}")

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

    return visited

在这个函数中，`graph`是一个键值对，键是节点，值是与其相连的节点列表。`visited`集合用于跟踪已访问过的节点，防止无限循环。函数首先标记起始节点为已访问，然后遍历其相邻节点，如果邻居节点未访问，就递归调用`dfs`函数。当遍历完所有邻居节点后，回到上一级节点，继续检查其他路径。