python如何写一个dfs函数

在Python中实现深度优先搜索（DFS）通常涉及到递归函数的编写。深度优先搜索是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这个过程一直进行到已发现从源节点可达的所有节点为止。

以下是一个简单的深度优先搜索函数的示例，用于遍历图结构：

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)  # 将起始节点标记为已访问
    print(start)  # 处理当前节点，例如打印节点值
    for next_node in graph[start]:  # 遍历所有邻接节点
        if next_node not in visited:
            dfs(graph, next_node, visited)  # 递归访问未访问的邻接节点
    return visited

# 示例图的邻接表表示
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# 开始深度优先搜索，从节点 'A' 开始
dfs(graph, 'A')

在这个例子中，`graph` 是一个字典，它的键是节点，值是与该节点直接相连的节点列表。`start` 是搜索的起点。`visited` 参数是一个集合，用来记录已访问过的节点，以避免重复访问。

DFS函数的工作流程如下：
1. 将当前节点标记为已访问，并对其进行处理（例如打印或添加到结果列表）。
2. 对于当前节点的每个未访问的邻接节点，递归调用DFS函数。
3. 重复这个过程，直到所有节点都被访问。