Learn-Algorithms 图论面试题全解：DFS/BFS 遍历、最短路径、割点与最大斜率直线

教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载图Graph是算法面试与工程实践中最高频的数据结构之一。本文以本仓库「9 Algorithms Job Interview/8 图.md」记录的经典面试题为骨架结合仓库内图论专题文档图的基础概念、DFS 和 BFS 搜索算法、最短路径算法展开系统讲解深度优先遍历DFS与广度优先遍历BFS的实现原理并逐一攻破三道高频面试题蜂窝结构图的最短路径搜索、有向连通图的割点求解、平面上斜率最大直线的查找。读完本文你将掌握图遍历的代码模板、最短路径算法的选型依据以及这类面试题的通用分析框架。一、图的基础先建立共同语言面试题中的图不是抽象概念而是由**顶点Vertex和边Edge**组成的数学模型顶点代表事物边表示事物之间的关系。本仓库 5 Graph/README.md 给出了三个必须先说清楚的基础概念有向图边有方向A→B 不代表 B→A例如关注关系、依赖关系。无向图边没有方向A-B 即 B-A例如朋友关系、交通路网。环首尾相接的路径。有环与无环直接决定能否使用拓扑排序等算法。图的工程应用场景非常广泛司机与乘客的匹配引擎、带优先级的并行任务调度、导航软件的路径规划路程最短/不走高速/时长最短、好友关系中的社区发现与精准营销、金融贷后催收中的失联人联系人修复等。理解了图描述的是关系这一本质再看遍历算法就顺理成章了。二、图的存储结构面试中先选对容器同样是图用不同方式存储代码复杂度和运行效率天差地别。本仓库 5 Graph/README.md 列出的三种存储方式对应三种代码写法对象和指针每个顶点是一个对象持有一组指向邻居的指针。直观但不利于批量计算。邻接矩阵二维数组graph[i][j]表示顶点 i 与 j 是否有边或边的权值。适合稠密图判断两点是否相邻为 O(1)但空间 O(V²)。邻接表每个顶点维护一个邻居列表。适合稀疏图遍历某点的所有邻居非常自然是面试中最常用的写法。在后续 DFS/BFS 代码中我们统一采用邻接表用vectorvectorint或ListListInteger表示这也是 leetcode 与工程中最常见的输入形态。三、深度优先遍历 DFS一条路走到底走不通就回溯本仓库 5 Graph/DFS 和 BFS.md 对 DFS 的描述非常精辟以深度为准则先一条路走到底直到达到目标没有达到目标又无路可走时则退回上一步的状态走其他路这便是回溯。DFS 天然用递归实现底层依赖栈结构系统调用栈遵循先进后出。DFS 的核心是每访问一个顶点就标记它已访问visited防止重复进入这是所有图遍历题的命门// 邻接表存储的图递归 DFS 模板 void dfs(int u, vectorvectorint adj, vectorbool visited) { if (visited[u]) return; visited[u] true; // 处理顶点 u 的业务逻辑如打印、统计、判目标 for (int v : adj[u]) { dfs(v, adj, visited); } }DFS 在面试中常用于全排列与组合枚举、迷宫/连通块求解、拓扑排序的 DFS 实现、以及是否存在一条从起点到终点的路径这类可达性问题。它的时间复杂度为 O(VE)空间复杂度最坏 O(V)递归栈深度。四、广度优先遍历 BFS逐层扩散先进先出仓库 5 Graph/DFS 和 BFS.md 同样生动地定义了 BFS在面临一个路口时把所有的岔路口都记下来然后选择其中一个进入再返回来进入另外一个岔路并重复这样的操作。BFS 用队列实现遵循先进先出天然适合求最短路径/最少步数——因为 BFS 按层扩散第一次到达目标节点的层数就是最短距离。// BFS 模板队列 visited void bfs(int start, vectorvectorint adj) { queueint q; vectorbool visited(adj.size(), false); q.push(start); visited[start] true; int depth 0; // 记录层数常用于最短步数 while (!q.empty()) { int size q.size(); // 当前层的节点数 for (int i 0; i size; i) { int u q.front(); q.pop(); // 处理顶点 u若 u 是目标节点depth 即最短步数 for (int v : adj[u]) { if (!visited[v]) { visited[v] true; q.push(v); } } } depth; } }BFS 的经典应用包括迷宫最短路径、单词接龙每个单词是一个顶点相差一个字母的单词之间连边、网络爬虫的分层抓取、以及社交网络的六度分隔。时间复杂度同为 O(VE)。五、最短路径算法蜂窝图面试题的武器库关联文档的第一道题类似蜂窝结构的图搜索最短路径5 分钟本质是带权或无权的图上求最短路。本仓库 5 Graph/最短路径.md 列出了可供选型的算法全家桶A* 算法静态路网中最有效的直接搜索方法用启发式函数距离估算值引导搜索估算值越接近真实值搜索越快。适合已知目标点的导航类场景。Dijkstra迪杰斯特拉解决图中单源点到其余各点的最短路径问题要求边权非负是工程与面试中使用率最高的算法。值得一提的是Dijkstra 是荷兰计算机科学家他同时提出了信号量与 PV 原语、哲学家就餐问题与死锁等著名概念。Floyd多源最短路三重循环动态规划适合顶点数较少的稠密图。Bellman-Ford / SPFA支持负权边可用于检测负权环但效率低于 Dijkstra。对蜂窝结构图而言若每个蜂窝之间的代价相同等价于无权图直接用 BFS 即可得到最短路径若移动代价不同则用 Dijkstra若已知目标位置且想要更快收敛则可升级为 A*启发式可用蜂窝中心点的欧氏距离/曼哈顿距离。这道5 分钟题考查的正是快速选型能力先判断边的权重类型再选择匹配的算法而不是盲目套用。六、面试题一蜂窝结构图的最短路径搜索华为蜂窝图可建模为规则网格的变体每个六边形有 6 个相邻蜂窝将其抽象为顶点相邻关系抽象为边就得到一个无向无权图。求解步骤将蜂窝编号映射为顶点构建邻接表六边形六个方向的邻居。若边权均等用 BFS 从起点逐层扩散首次到达终点时的层数即最短步数BFS 能保证最早到达即最短这是它的理论保证。若题目给每个蜂窝赋予穿越代价如地形、拥堵度改用 Dijkstra维护一个优先队列按当前累计代价最小优先扩展松弛每个邻居的代价。若在大型地图上追求效率可叠加 A* 启发式剪枝。参考仓库中 5 Graph/最短路径.md 的算法清单可以明确这道题的完整答题路径无权图 → BFS非负权图 → Dijkstra已知目标 静态路网 → A*。5 分钟之内能完成选型 写出核心循环即可通过。七、面试题二有向连通图的割点关节点题目原文如果除去此节点和与其相关的边有向图不再连通描述算法。割点Articulation Point / Cut Vertex是图论经典问题标准解法是 Tarjan 算法核心是用一次 DFS 同时算出两个关键值dfn[u]发现时间DFS 首次访问 u 的时间戳。low[u]回溯值从 u 出发通过 u 的子树中的边以及一条**回边back edge**能到达的最小发现时间。割点的判定规则若 u 是 DFS 树的根节点当 u 拥有≥2 个子树时u 是割点去掉 u 后各子树互相不连通。若 u 是非根节点存在一个子节点 v 满足low[v] dfn[u]即 v 的子树中没有任何边能绕回 u 的祖先去掉 u 后该子树将被孤立u 即为割点。void tarjan(int u, int parent) { dfn[u] low[u] timer; int childCount 0; for (int v : adj[u]) { if (v parent) continue; // 跳过父边 if (!dfn[v]) { // 未访问是树边 childCount; tarjan(v, u); low[u] min(low[u], low[v]); if (parent ! -1 low[v] dfn[u]) isCut[u] true; } else { low[u] min(low[u], dfn[v]); // 回边更新 low } } if (parent -1 childCount 2) isCut[u] true; // 根节点特殊判定 }面试时先答割点定义 → Tarjan 一次 DFS 求 dfn/low → 两条判定规则 → 复杂度 O(VE)即可完整体现对图论经典算法的掌握。注意题目说的有向图工程中还需区分强连通分量SCC语境Tarjan 同样可以处理只需在此基础上增加栈与是否在栈中的判定来求强连通分量。八、面试题三平面上 N 个点求斜率最大的直线题目原文平面上 N 个点每两个点都确定一条直线求出斜率最大的那条直线所通过的两个点斜率不存在的情况不考虑时间效率越高越好。这类题的关键是放弃 O(N²) 的暴力枚举利用排序后的几何性质最大斜率必然出现在按 x 坐标排序后相邻的两个点之间。证明思路任取三个点 A(x1,y1)、B(x2,y2)、C(x3,y3) 满足 x1 x2 x3设 AB、BC、AC 的斜率分别为 k1、k2、k3。可以推导出 k3 介于 k1 与 k2 之间几何上AC 的斜率是 AB 与 BC 斜率的加权平均因此全局最大斜率一定出现在某对相邻点上。算法步骤将 N 个点按 x 坐标排序复杂度 O(N log N)线性扫描一遍计算每对相邻点的斜率并记录最大值复杂度 O(N)总复杂度 O(N log N)远优于 O(N²)。sort(points, points n, byX); // 按 x 排序 double maxK -INF; Point a, b; for (int i 0; i n - 1; i) { double k (points[i1].y - points[i].y) / (points[i1].x - points[i].x); if (k maxK) { maxK k; a points[i]; b points[i1]; } }题目明确斜率不存在x 相等的情况不考虑因此可直接用上述除法若要稳健可在比较前特判dx 0。这道题考查的是将几何问题转化为排序 相邻扫描的思维能力是典型的高效算法设计题。九、图的延伸考点拓扑排序、二部图与最小生成树面试题往往从遍历延伸出去。本仓库的图论专题还收录了三个高频延伸主题建议与本文一并复习拓扑排序仅适用于有向无环图DAG用于任务调度、编译依赖排序。实现方式为 Kahn 算法不断删除入度为 0 的顶点或 DFS 后序逆序输出若过程中出现删不完的顶点说明图中有环。二部图二分图可用 BFS/DFS 染色法判定是匹配问题如司乘匹配、婚配问题的基础。最小生成树Prim类 Dijkstra适合稠密图与 Kruskal并查集 边排序适合稀疏图用于网络布线、连通成本最小化。A* / 启发式搜索详见 5 Graph/最短路径.md用于游戏编程与分布式计算中的路径规划。十、面试答题框架总结回顾 9 Algorithms Job Interview/8 图.md 的全部题目可以提炼出一套通用的图论面试答题流程建图先明确是有向图还是无向图、有权还是无权选择邻接表/邻接矩阵选遍历可达性、枚举、连通块 → DFS最短步数、层次扩散 → BFS选最短路无权 → BFS非负权 → Dijkstra已知目标 → A*含负权 → Bellman-Ford/SPFA多源全对 → Floyd经典算法扩展割点/强连通用 Tarjan拓扑排序用 Kahn 或 DFS匹配用染色法判定二部图复杂度的一页纸DFS/BFS 为 O(VE)Dijkstra 堆优化为 O((VE)logV)Tarjan 为 O(VE)排序类几何题常用 O(N log N)。把 DFS 和 BFS.md 中DFS 用栈递归、BFS 用队列这一句话记牢再配合本文给出的 DFS/BFS 代码模板、Tarjan 割点框架与排序几何证明本仓库收录的这几道图论面试题就能从容应对。建议对照 5 Graph/README.md 的应用场景章节将每个算法与真实业务调度、导航、社区发现、催收修复一一对应这既是面试加分项也是工程落地的正确姿势。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐Office.js未来展望了解API路线图和发展趋势Office.js未来展望了解API路线图和发展趋势 Office.js作为构建Office加载项的核心技术正通过持续的API更新和平台优化为开发者提供更前端API设计Ruby 图遍历实战用 BFS 实现骑士最短路径 knight_movesRuby 图遍历实战用 BFS 实现骑士最短路径 knight_moves 本文是 curriculum https://link.gitcode.com/i文档教程教育图论算法完全指南从BFS、DFS到最短路径的终极教程图论算法是计算机科学和编程面试中的核心内容掌握图论算法对于解决复杂问题至关重要。本文将为您详细介绍广度优先搜索 BFS 、深度优先搜索 DFS 以及各种最短路示例工程上一篇Mesh R-CNN完全解析ICCV 2019明星模型如何实现从2D图像到3D网格的革命性突破下一篇弹幕引擎黑科技用DanmakuFlameMaster实现炫酷3D滚动特效创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考