26｜图：深度优先遍历（DFS）与广度优先遍历（BFS）
王健伟
你好，我是王健伟。
上节课我们讲述了邻接矩阵、邻接表、十字链表、邻接多重表、边集数组共 5 种数据结构，解决了对图进行存储的问题。接下来的问题， 就是对图进行遍历了。
所谓图的遍历，就是指从图中任意一个顶点出发访遍图中其余顶点，且使每个顶点都被访问且只被访问一次。
图的遍历比树的遍历复杂很多，因为图中可能存在回路（环），因此遍历过程中需要标记每个已访问过的顶点以避免同一个顶点被访问多次。不过不用有什么负担，我会对照着代码给你讲透，这样既能理解，又方便你之后自己编写代码。
图的遍历通常分为两种：深度优先遍历、广度优先遍历。本节我们以邻接表作为图的存储结构来讲解这两种遍历。
深度优先遍历
深度优先遍历也称为深度优先搜索，英文名是 Depth First Search（DFS）。这种遍历其实是一个递归的过程，沿着每一个分支路径进行深入访问，很像一棵树的前序遍历。
你可以想象成进入到一个迷宫中，迷宫中有很多岔路，选择任意一条路走进去，一直到发现走不通的时候退回到上一个岔路口并重新选择一条路走进去，直到走遍所有关键节点。
针对前面用邻接表这种存储方式实现的图，我们可以在其中继续增加代码来实现对图的深度优先遍历。你可以看下相关的代码。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入介绍了图的遍历方法，着重讨论了深度优先遍历（DFS）和广度优先遍历（BFS）两种方法的实现和特点。DFS通过递归或栈实现，类似于树的前序遍历，而BFS则通过队列实现，从起始顶点开始逐层访问其邻接顶点。文章还详细阐述了使用邻接表作为图的存储结构来实现这两种遍历方法，并给出了它们的空间和时间复杂度。此外，文章还介绍了广度优先遍历的顺序以及非连通图的广度优先遍历方式。总之，本文为读者提供了深入了解和掌握图的遍历方法的基础知识，对于算法面试题也具有一定的指导意义。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论