python 深度优先算法实现

深度优先算法是一种搜索算法，它从一个起始节点开始，沿着一个路径一直到达最深的节点，然后返回上一个节点，继续搜索其他路径，直到找到目标节点或者所有节点都被搜索完毕。以下是 Python 中深度优先算法的实现：

1. 递归实现

def dfs_recursion(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next_node in graph[start] - visited:
        dfs_recursion(graph, next_node, visited)
    return visited

其中，`graph` 是一个字典，表示无向图的邻接表；`start` 是起始节点；`visited` 是已经访问过的节点集合。

2. 栈实现

def dfs_stack(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node)
            stack.extend(graph[node] - visited)
    return visited

其中，`graph` 是一个字典，表示无向图的邻接表；`start` 是起始节点；`visited` 是已经访问过的节点集合，初始为空；`stack` 是一个栈，初始节点为起始节点。每次从栈中弹出一个节点，如果该节点未被访问过，则将其加入已访问节点集合中，并将其未访问的相邻节点加入栈中。