大学本科计算机科学与技术专业二年级《数据结构与算法》深度优先搜索算法教案

大学本科计算机科学与技术专业二年级《数据结构与算法》深度优先搜索算法教案

一、教学目标

（一）知识与技能目标

引导学生深度建构深度优先搜索算法的核心概念体系，精准表述DFS作为图遍历与搜索基本范式的内涵，即从起始顶点出发，沿邻接点递归深入直至末端后回溯，系统访问图中所有可达顶点的过程。【基础概念】【重要】使学生熟练掌握图的两种主流存储结构——邻接矩阵与邻接表，并能基于此两种结构独立完成DFS递归代码的精准实现，清晰表述递归调用栈与系统栈的关联机制。【非常重要】【高频考点】要求学生掌握非递归DFS的实现原理，能够手动模拟栈数据结构以替代系统递归，完成显式栈版本的算法编写，从而深化对栈后进先出特性与算法执行流程对应关系的理解。【重要】【难点】培养学生运用DFS解决典型图论问题的迁移能力，涵盖无向图连通分量计数、有向图拓扑排序的逆后序实现、基于时间戳的Tarjan算法求强连通分量基础铺垫、二分图判定、迷宫路径搜索及树的重构等应用场景。【热点】【学科交叉】要求学生能准确推导DFS在邻接表与邻接矩阵两种实现下的时间复杂度与空间复杂度，明确O(V+E)与O(V²)的差异成因，并能结合具体问题优化存储策略。【基础】

（二）过程与方法目标

通过问题驱动与认知冲突创设，引领学生经历从“盲目搜索”到“系统遍历”的思维跃迁。以迷宫寻路、社交网络好友推荐等真实情境为锚点，引导学生在模拟手工走图的过程中自发归纳出“标记已访问”“深入探索”“无路回溯”三大DFS操作基元，完成从具体经验到抽象算法的概念提炼。【非常重要】在递归实现教学中，引导学生阅读并追踪递归函数执行轨迹，绘制递归调用树与栈帧变化图，培养程序动态调试与可视化分析能力。【重要】在非递归实现教学中，通过对比递归代码与显式栈代码的异同，引导学生洞察“栈”作为控制流管理工具的本质，提升算法抽象与等价转换思维。依托小组协作式编程任务，要求学生在限定时间内对特定图结构完成DFS遍历并输出遍历序列，在互评互改中锤炼代码调试与逻辑校验能力。通过布置开放式探究项目——如“基于DFS的在线棋局局面评估”“网页爬虫中的链接深度优先抓取策略”，促使学生将课堂算法迁移至跨学科真实问题解决场域，实现从算法执行者到算法设计者的角色过渡。【跨学科视野】【热点】

（三）情感态度与价值观目标

激发学生对算法之简洁美与逻辑之严密美的审美体验，使学生在调试递归代码从栈溢出到成功运行的过程中，形成迎难而上的工程意志与严谨求实的科学态度。【非常重要】在讲解DFS用于检测有向图环路进而保障编译器依赖关系合法性时，渗透技术对社会系统稳定性负责的工程师伦理意识。在小组协作环节，强化知识共享与批判性借鉴的同侪学习风尚，培育开放包容的学术交流品格。

二、教学重难点

（一）教学重点

深度优先搜索的递归实现逻辑及其与图存储结构的协同。【非常重要】【高频考点】具体包括：基于邻接表的递归DFS核心代码段——标记当前顶点、遍历其邻接点、对未访问邻接点递归调用自身；递归出口条件与遍历结束条件的区分；主函数中对非连通图各顶点循环调用DFS以确保全图访问的完备性策略。DFS遍历序列的生成顺序与递归树形态的对应关系。DFS在连通分量计数及环路检测等经典问题中的直接套用范式。【重要】

（二）教学难点

递归DFS背后隐含的系统栈工作机理与非递归DFS中显式栈的状态管理。【难点】【非常难】大量初学者虽能背诵递归代码，却无法在复杂递归嵌套中准确预测栈帧层叠与释放顺序，导致对回溯时机理解含混。非递归实现时，何时将顶点压栈、何时弹出、何时标记访问、压栈邻接点的顺序如何影响遍历序列，这四者之间的逻辑耦合极易引发编程错误。此外，DFS在强连通分量相关算法（如Kosaraju、Tarjan）中的前置应用涉及低链接、时间戳等进阶概念，是本课为后续课程铺设的隐性难点接口。对DFS生成树中树边、回边、前向边、横叉边的分类辨析，以及各类边在环路检测中的诊断价值，构成图论算法深水区的认知门槛。【跨课程衔接】

三、教学方法与手段

本课采用“认知学徒制”教学模式，将教师作为算法思维示范者与学生作为思维实践学徒的角色深度绑定。主干部分运用问题化讲授法，以连续追问驱动学生思维：例如先呈现无向连通图，提问“若用自然语言向一年级新生描述如何不重不漏走完所有顶点，你会分几步？”学生提炼出初步步骤后，教师将其符号化、结构化，演变为伪代码，最终落地为C/C++/Python可执行程序——全程展示从模糊需求到精确算法的知识生产流程。【非常重要】穿插使用溯源法，展示1960年代Hopcroft与Tarjan在深度优先搜索领域的原始论文思想片段，使学生理解算法并非既定教条，而是特定历史问题求解语境下的伟大创造。难点攻克采用“双码并置”策略：将递归DFS与非递归DFS代码并排投影，并以同一简单图为例同步单步执行，实时对比系统栈与手工栈的状态变迁，使栈的抽象本质具象化。全部授课过程融合板书手绘图结构、代码编辑器实时编码运行与内存可视化调试工具（如PythonTutor或GDB），形成“图景-代码-内存”三位一体的认知锚点。课堂组织形式包括10分钟微型讲座、20分钟师生协同编码、10分钟小组对拍纠错、5分钟概念地图建构。所有教学材料（板书矢量图、示例代码框架、半成品调试程序）均课前上传至校本SPOC平台，支持学生课前预跑与课后复现。【信息技术融合】

四、教学准备

教师准备：基于LaTexBeamer制作的矢量图形幻灯片，包含20张以上逐帧构建的图遍历过程动画；邻接表与邻接矩阵DFS递归与非递归四组标准参考代码（C语言版与Python双版）；内存可视化调试脚本；迷宫问题2D网格抽象图及对应邻接表生成器；五分钟微课视频《系统栈：递归背后的无名英雄》；课堂实时应答系统选择题库，涵盖DFS序列预测、复杂度计算、代码改错三类题型；便携数位板用于板书手绘递归调用树。学生准备：复习栈的ADT与递归函数执行过程；预习教材图存储结构章节；携带个人笔记本电脑并配置好C/Python编译运行环境；完成前测问卷，提交对“深度优先”四字的朴素理解。【基础】

五、教学实施过程（核心环节，逐阶展开）

（一）锚点引入与认知冲突创设（8分钟）

【情境浸入】教师展示一张本校校园地标建筑为节点、道路为边的拓扑地图，提出问题：“若你从图书馆出发，想要沿着道路探索所有从未去过的建筑，且每条路都必须完整走一遍不能中途折返，你能否设计一条不重复、不遗漏的行走策略？”学生以四人为小组在草图上试画，三分钟后邀请两组展示方案。【基础应用】第一组通常呈现类似“先走完一条路尽头，退回岔路口再走下一条”的朴素策略，教师立即板书抽象：此即“深度优先”的生活原型。第二组可能出现沿路标记已访问节点的行为，教师强调“标记”机制的核心地位。【生成性提炼】教师顺势将生活策略转化为半形式化步骤：1.站在当前节点，在节点上做个记号防止下次再来；2.查看从当前节点出发的所有未走过的道路；3.任选一条路，走到下一个节点；4.重复1-3；5.如果当前节点没有未走过的路了，就沿原路返回最近的有未走路口的节点。至此，学生已集体重演了DFS算法的发明历程。【非常重要】

【认知冲突】教师立即呈现一幅含有八个顶点、十条边的非连通图，要求各小组继续沿用上述策略。大部分小组发现“从图书馆出发”无法走到另一连通分量中的体育馆。认知冲突爆发：原始的“从单点出发”策略不能遍历全图！教师引入“多源启动”思想——在主函数中对所有顶点依次检查，若未被访问则以此为新起点调用DFS，从而彻底解决非连通图遍历完备性问题。此环节渗透了计算思维中“枚举所有可能性起点”的系统化考量。【难点扫清】【高频考点】

（二）新知系统建构与代码生成（25分钟）

1.递归DFS原型建构（15分钟）

【代码人类学】教师并不直接呈现教科书标准代码，而是以第一组学生的自然语言策略为蓝本，采用“结构化英语（StructuredEnglish）”逐句转译：第一步“站在当前节点”对应函数入口参数intv；第二步“做记号”对应设置visited[v]=1；第三步“遍历所有道路”对应循环结构遍历邻接点；第四步“若邻接点未访问，则以该点为参数调用自身”——递归结构在问题语境下自然涌现。【基础】【非常重要】教师通过四轮迭代，将结构化英语逐步精确为C语言函数原型，学生亲眼见证血肉丰满的代码诞生过程，彻底祛魅递归。

【双结构并置】教师在黑板左右分栏分别书写“邻接矩阵版DFS”与“邻接表版DFS”核心递归函数。左栏：voidDFS_AM(intv){visited[v]=1;for(inti=0;i<n;i++)if(arc[v][i]==1!visited[i])DFS_AM(i);}右栏：voidDFS_AL(intv){visited[v]=1;ArcNode*p=adjList[v].first;while(p){if(!visited[p->adjV])DFS_AL(p->adjV);p=p->next;}}教师引导学生对比两段代码差异：前者固定扫描所有顶点，时间必为O(V)；后者仅遍历实际邻接边，时间为O(度(v))。进而推导全图遍历总复杂度：邻接矩阵O(V²)，邻接表O(V+E)。【高频考点】【重要】教师此时以红粉笔加注星标：邻接表DFS是图论算法黄金搭档，必须形成条件反射。【非常重要】

【递归栈可视化】选取四顶点有向图1→2,1→3,3→4，请学生在笔记本上手动模拟DFS(1)全过程。教师调用PythonTutor，逐帧展示C语言递归函数调用栈的压入、悬停、返回、弹出过程。学生清晰看到：系统栈帧随递归调用层层叠加，随递归返回逐一释放，且栈顶始终是当前活跃的DFS现场。教师总结：递归版DFS的本质是编译器替你管理了回溯路径。这一可视化将90%初学者对递归的恐惧转化为直观认知。【难点突破】

2.非递归DFS显式栈实现（10分钟）

【工程需求引出】教师展示真实代码场景：某嵌入式图数据处理系统，编译器不支持函数递归调用。如何用有限资源实现深度优先搜索？学生立即意识到需要手动管理栈。【工程导向】教师以邻接表为例，逐步推导非递归算法，并刻意设置认知陷阱。初版伪代码：栈push(v);visited[v]=1;while(栈非空){v=栈顶;访问v;将v的所有未访问邻接点压栈;}运行演示发现：压入邻接点3,2后，栈顶是2，访问2并将2的邻接点压栈——造成“广度优先”的错觉！学生大笑，教师追问根源：深度优先要求“立即深入最新顶点”，而非将所有兄弟先行压栈。正确版本修正为：每次只将一个未访问邻接点压栈，并立即深度探索，或采用“延迟标记”法——顶点出栈时才标记访问。【难点】【非常难】教师提供标准非递归DFS骨架：栈s;s.push(v);while(!s.empty()){intx=s.top();if(!visited[x]){visited[x]=1;处理x;}//出栈时标记并访问ArcNode*p=adjList[x].first;inthasUnvisited=0;while(p){if(!visited[p->adjV]){s.push(p->adjV);hasUnvisited=1;break;}//仅压入一个，立即breakp=p->next;}if(!hasUnvisited)s.pop();//无未访邻接点则回溯}教师对比指出：此版本与递归版生成遍历序列严格一致，并通过动画展示栈内元素随深度增加而增长、回溯时下降的完美同步。【非常重要】【热点】

（三）知识结构化与概念图绘制（10分钟）

【师生共建概念拓扑】教师要求学生以“深度优先搜索”为中心节点，通过自由联想构建辐射状概念图。教师采集典型作品投影，并与全班共同增补、链接，最终形成包含五大模块的知识网络：1.前置基础（图存储、栈、递归）；2.核心机制（标记、深入、回溯、递归/非递归）；3.复杂度分析（时间、空间、不同存储结构差异）；4.遍历产物（DFS树、树边、回边、时间戳）；5.直接应用（连通分量、环检测、路径搜索）。【基础】教师在时间戳旁预留伏笔：“这是通往Tarjan算法的钥匙”。整张概念图以板书形式保留至下课，作为全课知识索引。【跨单元衔接】

（四）分层应用与迁移训练（20分钟）

【高频考点串讲与即时反馈】此环节采用“闯关式问题链”，每题要求学生在应答器或手写板上快速作答，正确率低于60%即展开即时辨析。

第一层：基础应用（全体必达）【基础】

题1.给定邻接表表示的无向图，从顶点0开始DFS，写出遍历序列（多种可能）。学生暴露对邻接点访问顺序的敏感度，教师强调“邻接表顺序决定遍历顺序”，但DFS逻辑框架不变。

题2.计算给定邻接矩阵图的DFS递归代码时间复杂度。95%学生能答O(V²)，再次巩固核心复杂度考点。

第二层：进阶应用（挑战性）【重要】

题3.利用DFS判别无向图是否连通，并输出连通分量个数。学生代码片段快速口述：主循环对每个顶点if(!visited[i]){count++;DFS(i);}。教师追加追问：如何改造以输出每个连通分量的顶点集？学生回答：在DFS(i)内将访问顶点打印或存入数组。教师点评：这是社交网络社区发现的最朴素原型。

题4.利用DFS判定二分图。教师提供二分图定义及染色法思想：给起始顶点染黑色，邻接点染白色，若DFS过程中发现某顶点邻接点已有同色，则非二分图。师生协同编写核心递归逻辑，教师强调此问题在调度系统、考试排考中的真实应用场景。【热点】【跨学科】

第三层：综合设计（高阶思维）【非常重要】【难点】

题5.迷宫最短路径？教师故意抛出争议命题。学生立即指出DFS不保证最短路径，BFS才是正解，但DFS可输出一条可行路径。教师展示二维网格转图模型，并引导学生实现DFS迷宫搜索，同时指出：若要输出所有路径或判断路径是否存在，DFS是极简方案。教师简要提及剪枝优化思想，为后续回溯法专题做铺垫。

（五）代码实战与对拍纠错（17分钟）

【结对编程】学生两人一组，一人主写递归DFS实现连通分量计数，另一人主写非递归DFS输出遍历序列。代码框架预置，学生仅需填充关键三至五行。教师巡视，捕获典型bug：1.邻接表创建时忘记设置next指针；2.visited数组未初始化；3.非递归版本中压入了已访问节点造成死循环；4.主循环对每个顶点调用DFS时未重置visited数组。【高频错误】教师选择三个典型错误现场投影，由全班共同“会诊”并修正，并由此总结防御性编程策略：初始化与资源释放必须成对检查；指针操作后立即验证非空；循环不变式需明确维护。【工程素养】

（六）跨学科视野拓展与前沿映射（5分钟）

【算法之用】教师播放30秒视频：波士顿动力公司Atlas机器人在复杂地形中，利用深度优先搜索策略规划脚步落点，探索可行走区域。学生惊呼算法进入物理世界。教师点明：机器人未知环境探索、网络爬虫的链接深度优先抓取策略、编程语言编译器中的依赖解析（循环import检测）、芯片设计中的电路网表连通性分析，其底层核心无一不是深度优先搜索。【非常重要】【跨学科】教师分发拓展阅读材料——1962年Tarjan关于深度优先搜索与强连通分量奠基性论文的第一页影印件（已译核心段落），让学生在历史语境中感受科学家如何从零到一构建知识大厦，激发学术志趣。

（七）全课收束与认知升维（5分钟）

【思维导图补完】教师带领学生在概念图外围添加元认知标注：DFS本质是“尝试-回溯-再尝试”这一通用问题求解策略在图结构上的具体投射。以哲学格言收尾：“递归是神性的，迭代是人性的——理解DFS，便理解了计算世界从何处来到何处去。”布置弹性作业：必做题为教