你接手一个权限可达性服务：授权图约 500 万节点、2000 万条有向边（用户→角色→权限组→资源），业务上允许成环。线上要回答『用户 u 能否到达资源 r』，峰值 10 万 QPS、P99 要求 20ms。上一版实现是每次请求从 u 出发做一次 DFS，线上大面积超时并偶发栈溢出。请给出你的方案、演进路径和取舍。

面试官在考什么

在给定图规模与 QPS 约束下，判断候选人是否会从『每次请求在线遍历』升级为『离线预计算 + 增量维护』，以及遍历实现细节的工程取舍。

图遍历

回答框架 · 前两步

1. 判断出在线单次遍历无法满足 20ms / 10 万 QPS，方案必须转向离线预计算（可达集合、SCC 缩点后的 DAG 传播、位图或区间标注）。
2. 先把有环图做 SCC 缩点转成 DAG，再按逆拓扑序做集合传播，避免在环上反复遍历。

延伸阅读

• 避坑与冲刺：简历自洽、六种扣分话术、D-7 准备表

想看这个方向的整体准备路线？ 进入「数据结构与算法」方向页

同一能力域的其他题

• 一个 N×N 的 0/1 网格，N=2000（共 400 万格），0 表示可通行，1 表示障碍，允许上下左右四方向移动，每走一格算 1 步。要求从 (0,0) 走到 (N-1,N-1)，给出最短步数，不可达返回 -1。内存上限 256MB。请说明你选 BFS 还是 DFS、队列和 visited 怎么设计、以及 visited 具体在什么时刻打标记。
• 社交关系图共 10^9 个用户，平均出度 200，边存放在分布式 KV 上（一次邻居查询约 5ms），单机可用内存 64GB。现在要找出指定用户 A 的 3 度以内（含 3 度）的全部用户 ID。你选 BFS 还是 DFS？写出你的遍历控制逻辑，估算 frontier（当前层待扩展集合）的最大规模，并说明用什么结构做去重。
• 给你一个 1000×1000 的 0/1 网格（1 是陆地，0 是水），上下左右相邻的陆地属于同一个岛，要求返回岛屿数量。A 同学用递归 DFS 做 flood fill，样例全过，但把规模放大到接近满屏陆地时程序崩溃。请说明崩溃的原因，写出你会怎么改；并说明同一份数据用 BFS 写时，队列规模的最坏情况是什么量级。
• 有向图有 4 个节点 s、a、b、t，边和权值是：s→a = 1，s→b = 2，b→a = -2，a→t = 3，b→t = 10。用朴素 Dijkstra（每次从未确定的节点里取 dist 最小的那个标记为已确定，之后不再更新它的 dist）从 s 求到 t 的最短路。请说出它算出的 dist[t] 是多少、正确答案是多少、差在哪一步上，然后说明什么样的图 Dijkstra 才是安全的。
• 一个城市路网约 10^8 个节点、2.5×10^8 条边，边权是通行时间（非负，但按早晚高峰每 5 分钟整体更新一次）。要支持单点到单点最短路查询、峰值 10^4 QPS、P99 延迟 < 50ms。朴素 Dijkstra 单次查询要扫描大量节点。你怎么选算法与架构？说清预处理成本、查询延迟、以及权重频繁变化带来的矛盾怎么权衡。
• 你负责一个路径规划服务：路网约 50 万节点、150 万条有向边，边权是通行时长且随早晚高峰变化，线上 2000 QPS，要在 50ms 内返回最快路径。当前实现是每个请求跑一次 Dijkstra。请说明你会怎么演进这个系统，以及每一步的代价。