python 图的遍历dfs

深度优先搜索（Depth-First Search，DFS）是图论中的一个常用算法，用于遍历或搜索树和图的数据结构。在Python中，我们可以使用内置的数据结构和堆栈（stack）来实现DFS。以下是一个基本的DFS遍历图的例子，假设我们有一个用邻接列表表示的无向图：

def dfs(graph, start_node):
    visited = set()  # 用于存储已经访问过的节点
    stack = [start_node]  # 初始化堆栈，将起始节点推入

    while stack:  # 只要堆栈不为空
        node = stack.pop()  # 弹出当前节点
        if node not in visited:  # 如果该节点未访问过
            visited.add(node)  # 标记为已访问
            print(node, end=" ")  # 输出节点值
            # 推入未访问的邻居节点
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

# 假设我们有这样一个简单的图：
# graph = {
#     'A': ['B', 'C'],
#     'B': ['D', 'E'],
#     'C': ['F'],
#     'D': [],
#     'E': ['F'],
#     'F': []
# }
dfs(graph, 'A')  # 从'A'开始遍历

运行上述代码，将按照DFS的方式输出节点序列：A B D E F C。