当前位置：首页 > news >正文

深度优先与广度优先遍历：图论算法终极指南与面试技巧

news 2026/5/26 22:24:02

深度优先与广度优先遍历：图论算法终极指南与面试技巧

【免费下载链接】CodingInterviewChinese2《剑指Offer：名企面试官精讲典型编程面试题》第二版源代码项目地址: https://gitcode.com/gh_mirrors/co/CodingInterviewChinese2

深度优先搜索（DFS）和广度优先搜索（BFS）是图论算法中最核心的两种遍历方法，也是《剑指Offer：名企面试官精讲典型编程面试题》第二版中重点讲解的面试高频考点。这两种遍历算法不仅是解决图论问题的基础，更是许多复杂算法（如最短路径、拓扑排序、连通分量）的基石。对于准备技术面试的开发者来说，掌握深度优先与广度优先遍历的原理和应用场景，是提高算法能力、通过名企面试的关键一步。

📊 为什么深度优先与广度优先如此重要？

在编程面试中，图论算法和树遍历问题占据了相当大的比重。无论是二叉树的各种遍历方式，还是图的最短路径问题，都离不开DFS和BFS这两种基础算法。

🔍 深度优先搜索（DFS）的核心思想

深度优先搜索采用递归或栈的方式，沿着一条路径深入探索，直到无法继续前进，然后回溯到上一个节点继续探索其他分支。这种"一条路走到黑"的策略非常适合解决：

路径查找问题：如迷宫问题、图的连通性判断
回溯算法：如八皇后问题、全排列问题
拓扑排序：有向无环图的排序问题

🌐 广度优先搜索（BFS）的核心思想

广度优先搜索采用队列的方式，从起点开始，逐层向外扩展，先访问所有相邻节点，再访问下一层节点。这种"层层推进"的策略特别适合解决：

最短路径问题：无权图的最短路径
层次遍历：二叉树的层序遍历
状态空间搜索：如单词接龙、最小基因变化

🎯 面试中的高频应用场景

二叉树相关问题

在《剑指Offer》中，二叉树相关的问题占据了重要位置：

二叉树的深度优先遍历：前序、中序、后序遍历
二叉树的广度优先遍历：层序遍历
二叉树的最大深度：55_01_TreeDepth/TreeDepth.cpp
平衡二叉树判断：55_02_BalancedBinaryTree/BalancedBinaryTree.cpp

图论相关问题

虽然《剑指Offer》中直接的图论问题相对较少，但许多问题都可以转化为图论模型：

矩阵中的路径搜索：12_StringPathInMatrix/StringPathInMatrix.cpp
机器人运动范围：13_RobotMove/RobotMove.cpp

💡 实用技巧与优化策略

1. 记忆化搜索

在深度优先搜索中，经常会遇到重复计算的问题。通过记忆化搜索（Memoization）可以显著提高效率：

// 示例：斐波那契数列的DFS优化 int fibonacci(int n, vector<int>& memo) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo); return memo[n]; }

2. 双向BFS优化

对于某些搜索问题，从起点和终点同时进行BFS搜索，可以大幅减少搜索空间：

应用场景：单词接龙、最短转换序列
优势：将时间复杂度从O(b^d)降低到O(b^{d/2})

3. 剪枝策略

在DFS回溯过程中，合理的剪枝可以避免大量无效搜索：

可行性剪枝：当前状态已经不可能达到目标
最优性剪枝：当前路径已经比已知最优解差
重复状态剪枝：避免重复访问相同状态

📈 面试实战演练

案例1：二叉树的层序遍历

// 参考：[32_01_PrintTreeFromTopToBottom/PrintTreeFromTopToBottom.cpp](https://link.gitcode.com/i/486f82d784d89b54010a9721b26031cb) vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; if (!root) return result; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int levelSize = q.size(); vector<int> level; for (int i = 0; i < levelSize; i++) { TreeNode* node = q.front(); q.pop(); level.push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } result.push_back(level); } return result; }

案例2：图的DFS遍历

// 参考：[26_SubstructureInTree/SubstructureInTree.cpp](https://link.gitcode.com/i/a687c4876f64f3f549730ff30f01ce94) void dfs(vector<vector<int>>& graph, int node, vector<bool>& visited) { visited[node] = true; for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfs(graph, neighbor, visited); } } }