# 作业：深度优先搜索（DFS） ## 程序概述 本程序实现了**深度优先搜索（Depth-First Search, DFS）**算法，用于遍历或搜索图结构。DFS 是一种递归或栈实现的遍历方式，优先深入探索每一个分支。 --- ## 头文件信息 ```python """ 来源：CSDN与合作伙伴AI教学项目 平台：Python IDLE / VS Code / Jupyter Notebook 版本：Python 3.10+ 简介：该程序演示了深度优先搜索算法在图结构中的应用 姓名：张三 时间：2025年4月5日 """ ``` --- ## Python代码及解析 ### 完整代码段： ```python def dfs(graph, start, visited=None): if visited is None: visited = set() # 初始化已访问集合 visited.add(start) # 标记当前节点为已访问 print(start, end=' ') # 打印当前访问的节点 for neighbor in graph[start]: # 遍历当前节点的所有邻居 if neighbor not in visited: # 如果邻居未被访问过 dfs(graph, neighbor, visited) # 递归访问邻居节点 # 图的邻接表表示 graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'G'], 'F': ['C'], 'G': ['E'] } # 调用DFS从节点'A'开始 dfs(graph, 'A') ``` --- ### 代码逐条注释： ```python def dfs(graph, start, visited=None): # 定义DFS函数，参数为图、起始点和已访问集合 if visited is None: # 若是首次调用，则初始化visited集合 visited = set() # 使用集合存储已访问节点，保证唯一性 visited.add(start) # 将当前节点加入已访问集合 print(start, end=' ') # 输出当前节点 for neighbor in graph[start]: # 遍历当前节点的所有邻居 if neighbor not in visited: # 如果邻居未被访问 dfs(graph, neighbor, visited) # 递归调用DFS继续深入搜索 ``` --- ## 运行结果 ``` A B D E G C F ``` > 注：输出顺序取决于邻接表中节点的排列顺序，例如 `'B'` 出现在 `'C'` 前面，所以会先访问 `B` 及其所有子节点。 --- ## 知识点 1. **图的邻接表表示法** - 用字典结构描述每个节点及其连接关系，便于查找邻居节点。 2. **递归函数设计** - 使用递归模拟栈的行为，深入访问图的每一个可达节点。 3. **集合(set)数据结构操作** - 利用集合的 `add()` 和 `in` 操作来高效记录和判断节点是否已被访问。