2025 高中信息技术数据与计算之算法的图的遍历算法课件

一、引言：为何要学习图的遍历算法？演讲人目录教学实践：如何让学生掌握图的遍历算法？核心算法：深度优先搜索（DFS）与广度优先搜索（BFS）图的遍历算法基础：从概念到核心目标引言：为何要学习图的遍历算法？总结：图的遍历——算法思维的启蒙钥匙543212025高中信息技术数据与计算之算法的图的遍历算法课件01引言：为何要学习图的遍历算法？引言：为何要学习图的遍历算法？作为高中信息技术“数据与计算”模块的核心内容之一，图的遍历算法是连接数据结构与算法设计的关键桥梁。我在多年教学中发现，许多学生在接触图结构时，常因“如何系统访问所有节点”而困惑——这就像在陌生城市中寻找所有景点，没有路线规划就会遗漏或重复。而图的遍历算法（TraversalofGraph）正是解决这类问题的“导航仪”：它通过特定规则访问图中每个顶点一次且仅一次，不仅能帮助我们理解图的结构特性，更为后续学习最短路径、拓扑排序、连通分量分析等高级算法奠定基础。02图的遍历算法基础：从概念到核心目标1图的基本结构回顾要理解遍历算法，首先需明确图的核心要素。图（Graph）由顶点（Vertex，简称V）和边（Edge，简称E）组成，记作G=(V,E)。根据边的方向性，可分为无向图（边无方向，如微信好友关系）和有向图（边有方向，如微博关注关系）；根据边的权重，可分为无权图（边无权重，如简单连接）和带权图（边有权重，如地图中路段距离）。在高中阶段，我们主要研究无权图的遍历，其存储方式通常有两种：邻接矩阵：用二维数组存储顶点间的连接关系，空间复杂度为O(n²)，适合顶点数较少（n≤100）的图；邻接表：用链表或数组存储每个顶点的邻接顶点，空间复杂度为O(n+e)（e为边数），适合稀疏图（边数远小于n²）。例如，一个包含4个顶点（A、B、C、D）的无向图，若A与B、C相连，B与D相连，其邻接矩阵可表示为：1图的基本结构回顾ABCDA0110B1001C1000D0100邻接表则为：A→B→C；B→A→D；C→A；D→B。2遍历的定义与核心目标0504020301图的遍历是指从图中某一顶点出发，按照某种规则依次访问其余顶点，且每个顶点仅被访问一次的过程。其核心目标有三：完整性：确保所有可达顶点被访问（针对非连通图，需对每个连通分量单独遍历）；无重复：通过标记已访问顶点避免循环访问（如A→B→A的死循环）；规则性：遍历顺序由具体算法（如DFS/BFS）决定，体现不同的搜索策略。例如，在班级同学关系图中（无向图），若以“我”为起点遍历所有同学，需确保每个同学被“访问”（如打招呼）一次，且路径符合算法规则。03核心算法：深度优先搜索（DFS）与广度优先搜索（BFS）核心算法：深度优先搜索（DFS）与广度优先搜索（BFS）图的遍历主要有两种经典算法：深度优先搜索（Depth-FirstSearch,DFS）和广度优先搜索（Breadth-FirstSearch,BFS）。二者的本质区别在于搜索策略——DFS“一条路走到底”，BFS“逐层扩展”。1深度优先搜索（DFS）1.1算法原理与步骤DFS的核心思想是“先深入，后回溯”：从起始顶点出发，访问其未访问的邻接顶点，递归深入直到无法继续，再回溯到上一顶点，继续探索其他未访问邻接顶点。这一过程类似“走迷宫”时优先选择一条通道，走到死胡同后返回岔路口尝试其他通道。具体步骤（以无向图为例）：初始化：标记所有顶点为未访问（如用数组visited[v]=false）；选择起始顶点v，标记为已访问（visited[v]=true），并记录访问顺序；遍历v的所有邻接顶点u：若u未被访问，则递归调用DFS(u)；若u已被访问，跳过；递归结束条件：当前顶点的所有邻接顶点均已访问。1深度优先搜索（DFS）1.2实现示例与代码分析以图3-1为例（顶点A为起点，邻接关系：A-B,A-C,B-D,C-E,D-E）：1手动模拟遍历过程：2步骤1：访问A（标记为已访问）；3步骤2：选择A的邻接顶点B（未访问），访问B；4步骤3：选择B的邻接顶点D（未访问），访问D；5步骤4：选择D的邻接顶点E（未访问），访问E；6步骤5：E的邻接顶点为C（未访问），访问C；7步骤6：C的邻接顶点A（已访问）、E（已访问），回溯到E；8步骤7：E的所有邻接顶点已访问，回溯到D；91深度优先搜索（DFS）1.2实现示例与代码分析步骤8：D的所有邻接顶点已访问，回溯到B；1步骤10：A的邻接顶点C（未访问？不，步骤5已访问C），遍历结束。2最终访问顺序：A→B→D→E→C。3Python代码实现（递归版）：4defdfs(graph,v,visited,path):5visited[v]=True6path.append(v)7foruingraph[v]:8ifnotvisited[u]:9步骤9：B的邻接顶点A（已访问）、D（已访问），回溯到A；101深度优先搜索（DFS）1.2实现示例与代码分析dfs(graph,u,visited,path)01邻接表表示的图（顶点用0-4编号，对应A-E）02graph={030:[1,2],#A邻接B(1)、C(2)041:[0,3],#B邻接A(0)、D(3)052:[0,4],#C邻接A(0)、E(4)063:[1,4],#D邻接B(1)、E(4)071深度优先搜索（DFS）1.2实现示例与代码分析4:[2,3]#E邻接C(2)、D(3)}visited=[False]*5path=[]dfs(graph,0,visited,path)print("DFS访问顺序:",path)#输出：[0,1,3,4,2]（对应A→B→D→E→C）1深度优先搜索（DFS）1.3复杂度分析与应用场景1时间复杂度：每个顶点被访问一次，每条边被访问两次（无向图）或一次（有向图），故时间复杂度为O(n+e)（n为顶点数，e为边数）；2空间复杂度：递归栈的最大深度为图的深度，最坏情况（链状图）为O(n)；3典型应用：连通性检测（如判断图是否连通）、拓扑排序（有向无环图）、寻找所有路径（如迷宫所有可行路线）。2广度优先搜索（BFS）2.1算法原理与步骤BFS的核心思想是“逐层扩展”：从起始顶点出发，先访问其所有邻接顶点（第一层），再依次访问这些邻接顶点的未访问邻接顶点（第二层），依此类推，直到所有顶点被访问。这一过程类似“波纹扩散”，逐层向外扩展。具体步骤（以无向图为例）：初始化：标记所有顶点为未访问，创建队列并将起始顶点入队；当队列不为空时：出队顶点v，标记为已访问，记录访问顺序；遍历v的所有邻接顶点u：-若u未被访问，标记为已访问（避免重复入队），并将u入队；结束条件：队列为空（所有可达顶点已访问）。2广度优先搜索（BFS）2.2实现示例与代码分析仍以图3-1为例（顶点A为起点）：手动模拟遍历过程：步骤1：队列初始化[0（A）]，标记0为已访问；步骤2：出队0，记录路径[0]，邻接顶点1（B）、2（C）未访问，入队[1,2]；步骤3：出队1（B），记录路径[0,1]，邻接顶点0（已访问）、3（D）未访问，入队[2,3]；步骤4：出队2（C），记录路径[0,1,2]，邻接顶点0（已访问）、4（E）未访问，入队[3,4]；2广度优先搜索（BFS）2.2实现示例与代码分析步骤5：出队3（D），记录路径[0,1,2,3]，邻接顶点1（已访问）、4（E）未访问（但E是否已被标记？此时E未被访问吗？不，步骤4中C的邻接顶点4未访问，所以步骤4将4入队前已标记为已访问）；（注：正确流程应为：步骤4出队2（C）时，邻接顶点4（E）未访问，标记为已访问并加入队列，此时队列变为[3,4]；步骤5出队3（D），其邻接顶点4（E）已被标记，跳过；步骤6出队4（E），记录路径[0,1,2,3,4]。）最终访问顺序：A→B→C→D→E。Python代码实现（迭代版）：fromcollectionsimportdequedefbfs(graph,start):2广度优先搜索（BFS）2.2实现示例与代码分析01visited=[False]*len(graph)02visited[start]=True03path=[]04whilequeue:05v=queue.popleft()06path.append(v)07foruingraph[v]:08ifnotvisited[u]:09visited[u]=True10queue=deque([start])2广度优先搜索（BFS）2.2实现示例与代码分析queue.append(u)returnpath2广度优先搜索（BFS）同一图结构graph={0:[1,2],1:[0,3],2:[0,4],3:[1,4],4:[2,3]}print("BFS访问顺序:",bfs(graph,0))#输出：[0,1,2,3,4]（对应A→B→C→D→E）2广度优先搜索（BFS）2.3复杂度分析与应用场景时间复杂度：同DFS，为O(n+e)；空间复杂度：队列的最大长度为图的宽度，最坏情况（星型图）为O(n)；典型应用：最短路径（无权图中两点间最短路径）、层序遍历（如社交网络中的“一度好友→二度好友”）、连通分量划分（多源BFS）。3DFS与BFS的对比与选择|维度|DFS|BFS||--------------|------------------------------|------------------------------||搜索策略|深度优先，递归或栈实现|广度优先，队列实现||访问顺序|先深入后回溯，路径较长|逐层扩展，路径较短||空间复杂度|与深度相关（O(n)）|与宽度相关（O(n)）||适用场景|连通性检测、拓扑排序、路径枚举|最短路径、层序分析、多源扩散||教学难点|递归理解、回溯过程|队列操作、层级标记|例如，在“寻找从A到E的所有路径”问题中，DFS更高效（递归自然枚举所有可能路径）；而在“求A到E的最短路径”问题中，BFS更合适（首次到达E时即为最短路径）。04教学实践：如何让学生掌握图的遍历算法？教学实践：如何让学生掌握图的遍历算法？作为一线教师，我发现学生在学习图的遍历时，常遇到“能听懂但写不出代码”“混淆DFS与BFS顺序”等问题。以下是我的教学策略总结：1直观化演示：从手动模拟到动画辅助手动模拟：用黑板绘制简单图（如4-5个顶点），让学生分组扮演“访问者”，按DFS/BFS规则轮流选择下一个顶点，记录路径。例如，用“教室座位图”（顶点为学生，边为相邻关系）进行现场模拟，学生能直观感受“深度”与“广度”的区别。动画工具：使用VisuAlgo（）等在线平台演示遍历过程，动态展示栈/队列的变化，帮助学生理解抽象的“递归回溯”和“队列扩展”。2代码实践：从模板到变式基础模板：先让学生掌握邻接表/邻接矩阵的存储方式，再编写DFS（递归/迭代）和BFS的基础代码。例如，用Python的列表和deque实现队列，强调“标记已访问”的关键作用（避免死循环）。变式训练：通过“计算连通分量个数”“判断是否为树（无环连通图）”等问题，引导学生将遍历算法应用到实际问题中。例如，对于非连通图，需对每个未访问顶点调用遍历算法，统计连通分量数。3常见误区与解决误区1：忘记标记已访问顶点。例如，在DFS中未设置visited数组，导致循环访问（如A→B→A）。解决方法：强调“访问即标记”的原则，通过错误代码示例（如注释掉visited[v]=True）演示后果。01误区2：混淆DFS的递归终止条件。例如，认为“当顶点无邻接顶点时返回”，但实际上递归终止条件是“所有邻接顶点已访问”。解决方法：通过单步调试递归代码，观察栈的调用过程。02误区3：BFS中重复入队。例如，在将邻接顶点入队时未标记已访问，导致同一顶点多次入队（如顶点E被B和C同时入队）。解决方法：强调“入队即标记”，确保每个顶点仅入队一次。0305总结：图的遍历——算法思维的启蒙钥匙总结：图的遍历——算法思维的启蒙钥匙图的遍历算法不仅是高中信息技术的核心知识点，更是培养计算思维的重要载体。通过DFS的“探索精神”和BFS的“全局视野”，学生能深刻理解“问题分解”“抽象建模”“算法优化”等计算思维要素。回顾全文，我们从图的基本结构出发，逐步解析了DFS与BFS的原理、实现与应用，对比了二者的差异，并探讨了教