扫码获取 VIP 码
添加管理员微信获取 VIP 码
图的遍历是图论中最基础的操作之一，也是软件设计师考试中每年必考的核心知识点。无论是判断图的连通性、求生成树、拓扑排序，还是更复杂的最短路径和关键路径问题，都建立在深度优先搜索与广度优先搜索这两大遍历策略之上。掌握这两种遍历算法不仅意味着能写出正确的遍历序列，更要求理解其背后的数据结构支撑——邻接矩阵和邻接表的选择如何影响算法的时间效率与空间开销，以及在递归与迭代两种实现路径中如何避免常见陷阱。本文从图的存储结构出发，逐层深入到DFS的递归与栈实现、BFS的队列驱动机制，并结合历年软考真题剖析命题人的挖坑套路与解题核心思路。
在进入算法细节之前，必须先建立图的精确概念模型。图是比线性表和树更为复杂的非线性数据结构，它的形式化定义是一个二元组，包含顶点集合和边集合两个要素。设图记作G等于V和E组成的有序对，其中V是非空的顶点有限集合，E是连接这些顶点的边的有限集合。根据边是否具有方向性，图可以划分为无向图和有向图两大类。无向图中的边用无序偶对表示，意味着从顶点A到顶点B的访问与从B到A的访问在逻辑上等价；有向图中的边则用有序偶对表示，表示一条从起点指向终点的有向弧，方向约束严格不可逆。
除了方向性之外，边的权重也是图的另一个重要属性。带权图也称为网络，每条边上附加一个数值表示代价、距离或容量。在软考命题中，带权图通常与最小生成树、最短路径等经典问题绑定出现。与顶点相关的术语同样不容忽视：度是依附于某顶点的边的条数，在有向图中进一步分化为出度和入度；路径定义为顶点序列中相邻顶点之间均有边相连的序列，简单路径要求路径上的顶点不重复出现；回路或环是首尾顶点相同的路径；连通性则描述图中任意两个顶点之间是否存在通路，连通分量是极大连通子图的个数。此外，生成树是包含图中所有顶点且边数最少的连通子图，生成森林则是非连通图中每个连通分量各取一棵生成树构成的集合，这些概念是理解DFS和BFS衍生应用如最小生成树和拓扑排序的基础前提。
理解这些术语的形式化含义对于正确解题至关重要。许多考生在处理遍历问题时出错，根源往往在于对连通和完全图等概念的理解停留在感性层面，而未能从定义出发严谨推演。例如，含有N个顶点的无向完全图的边数是N乘以N减一的乘积除以二，有向完全图则是N乘以N减一，这些公式不是凭空记忆的产物，而是顶点之间两两相连的排列组合结论。软考选择题中经常要求考生从给定的顶点度和边数反推图的类型，此时对基本定义和计数公式的熟练掌握就直接决定了答题的速度和准确率。考生还可以借助握手定理来快速验证：无向图中所有顶点的度之和等于边数的两倍，这一性质在检查题目条件是否合理时极为有效。
将图的拓扑结构映射到计算机内存中，主要有两种经典方案：邻接矩阵和邻接表。这两种存储方式在空间复杂度、边查询效率和遍历性能上各有优劣，选择哪一种存储结构会直接影响后续DFS与BFS算法的时间复杂度。在软考真题中，判断某种存储方式适合稠密图还是稀疏图是高频考点，考生必须理解两种结构底层的工作原理而非死记结论。
邻接矩阵用一个N行N列的二维数组存储N个顶点的图，数组元素A的第i行第j列取值表示顶点i到顶点j之间是否存在边。对于无向图，矩阵沿主对角线对称，只需存储上三角或下三角即可节约一半空间；对于带权图，矩阵元素可以直接存储边的权值，不存在的边用无穷大或特殊标记填充。邻接矩阵的突出优势在于边查询操作的时间复杂度为常数级别，判断任意两个顶点之间是否相邻只需一次数组下标访问即可完成。此外，计算顶点的度同样高效——无向图中遍历对应行统计非零元素的个数，有向图中行和对应出度而列和对应入度。
然而邻接矩阵的空间效率存在明显的适用边界。无论图中有多少条边，矩阵都需要固定占用N的平方个存储单元。对于边数远小于完全图中的顶点数的稀疏图——例如社交网络中的好友关系，数十万用户之间真正的连接往往只有百万量级——邻接矩阵会浪费大量存储空间，导致遍历时空开销严重膨胀。软考命题中经常结合图的稠密与稀疏特性，要求考生判断在给定场景下应选择邻接矩阵还是邻接表，此时必须同时考虑图的规模和边密度两个维度。一个实用的判断标准是：当边的数量接近或超过顶点数平方的一半时，邻接矩阵在时间和空间上均具备优势；反之邻接表更为经济。
邻接表为每个顶点维护一个线性链表或动态数组，表中存储该顶点的所有邻接顶点。对于有向图，每个顶点的邻接表只存储由该顶点出发的有向边的终点，因此空间复杂度与图中的边数呈线性关系，远优于邻接矩阵在处理稀疏图时的平方级消耗。对于无向图，每条边会在两个端点的邻接表中各出现一次，因此总存储量为边数的两倍，仍然保持线性级别。
邻接表在边查询上的代价则明显高于邻接矩阵。判断两个顶点是否相邻需要遍历其中一个顶点的邻接表，最坏情况下的时间复杂度与顶点的度成正比。这一特性使得邻接表更适合以遍历为核心操作的应用场景——DFS和BFS在邻接表上的时间复杂度为顶点数加边数之和，这种线性复杂度在处理大规模稀疏图时表现极佳。软考选择题中有时会给出一个具体的图结构，要求考生分析在不同存储表示下DFS遍历路径的差异，这类题目考查的正是对两种存储结构内部数据组织方式的深入理解。邻接表还有一个值得注意的变体是逆邻接表，专门用于有向图中快速查询指向某个顶点的入边，在处理入度相关问题时可以显著降低时间开销，这也是拓扑排序算法中Kahn算法的核心数据结构。
深度优先搜索是图遍历中最经典也最能体现回溯思想的算法。它的核心策略可以概括为一条路走到黑：从起始顶点出发，沿着一条未被访问的边深入访问下一个顶点，再以新顶点为起点继续深入，直到无法继续前进时回溯至上一个顶点，再尝试其他未被探索的分支。这种先纵向深入再横向回退的策略天然适合用递归来实现，因为递归函数的调用栈正好模拟了深入与回溯的过程。
在DFS的执行过程中，维护一个访问标记数组是确保算法正确性的绝对前提。没有访问标记，算法会在包含环路的图中陷入无限循环。访问标记的设置时机直接影响遍历结果：标记应该在顶点即将被访问时设置，而非在顶点出栈或回溯时。如果标记设置过晚，同一个顶点可能被重复加入遍历序列，导致结果中出现冗余。递归实现的DFS代码极其简洁——对当前顶点的每个邻接顶点，若该邻接顶点尚未被访问，则递归调用DFS函数继续探索。递归的深度在最坏情况下可达顶点数减一，这意味着对于深度极大的图，递归实现有导致调用栈溢出的风险。在软考中，这一特性经常与系统栈空间限制结合考查，要求考生评估递归方案在特定图结构下的可行性。
显式栈实现的DFS将递归改为手动维护一个栈结构，本质上与递归版本等价，但提供了对遍历过程的更精细控制。先将起始顶点入栈并标记已访问，然后进入循环：弹出栈顶顶点作为当前访问节点，遍历其所有邻接顶点，将尚未访问的邻接顶点入栈并标记。需要注意的是，显式栈版本的遍历序列可能与递归版本不完全相同，这取决于邻接顶点的入栈顺序——由于栈的后进先出特性，先入栈的邻接顶点反而会被后访问。软考真题中频繁出现的给定图结构和起始顶点写出DFS遍历序列类题目，正是对考生理解遍历顺序确定性的考查。深度优先搜索同时会生成一棵DFS生成树，树上的边对应遍历过程中第一次发现某个顶点时所经过的边，而其余的边——连接两个已在DFS生成树上的顶点但未被用作发现新顶点的边——被称为回边或交叉边，它们的出现表明图中存在环路。在无向图中，如果DFS遍历过程中遇到一条指向已访问顶点但不是其父顶点的边，即可判定该图包含环。
广度优先搜索采用与DFS截然不同的逐层推进策略。从起始顶点开始，先访问所有与起始顶点距离为一跳的顶点，再访问距离为两跳的顶点，以此类推，形成以起始顶点为中心的同心圆式扩展。这种层次化的遍历逻辑使得队列成为BFS最自然的辅助数据结构——当前层的顶点依次出队进行
本篇完！