python 深度优先遍历

深度优先遍历（DFS）是一种用于遍历或搜索树或图的算法。在深度优先搜索中，我们从起始节点开始，沿着树的深度尽可能深地探索，直到到达叶子节点或者无法继续探索为止。然后回溯到上一个节点并继续探索其他的分支。这个过程会一直进行下去，直到遍历到所有的节点为止。在Python中，可以使用递归或者使用栈（Stack）来实现深度优先遍历。

以下是一个使用递归实现深度优先遍历的示例代码：

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # 输出当前节点
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

在这个示例中，`graph`表示图的邻接表，`start`表示起始节点。`visited`是一个集合，用于记录已经访问过的节点。在每次递归调用中，我们先将当前节点加入到`visited`集合中，并输出当前节点。然后递归地遍历当前节点的邻居节点，如果邻居节点尚未被访问过，则进行递归调用。

如果你想使用栈来实现深度优先遍历，可以使用以下示例代码：

def dfs(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)

在这个示例中，我们使用了一个栈`stack`来保存待访问的节点。初始时，将起始节点`start`压入栈中。然后，循环执行以下操作：弹出栈顶节点`node`，如果`node`尚未被访问过，则将其加入到`visited`集合中，并输出`node`；然后将`node`的未访问邻居节点加入到栈中。这样循环进行，直到栈为空。