微服务调用关系中找最短调用链
哪些公司问过
答案要点
- 服务为节点、调用为有向边建图
- 入口服务为入度为 0 的节点,统计入度即可找到
- 无权图用 BFS 求最短链,可多源同时入队
- visited 防止循环调用死循环,parent 数组回溯路径
- 时间 O(V+E),带耗时权重时改用 Dijkstra
易错点
- 没有 visited,循环调用导致死循环
- 用 DFS 第一次找到的路径当最短路径
- 只返回长度而没有记录路径
面试官常见追问
- 如何检测服务间是否存在循环调用?
- 如果要找最长调用链呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。