标签题目
图论相关面试题
图论算法具体有哪些？
这题考察图问题分类能力，要把问题类型、适用条件、图表示和复杂度一起说，而不是背算法名清单。
A* 相比 Dijkstra 优化了什么问题？
A* 主要优化的是 Dijkstra 在单源到单目标最短路径场景中的均匀扩展问题。Dijkstra 只按当前已知代价 g(n) 从近到远扩展，不利用终点方向信息，因此会探索大量与目标无关但距离起点较近的节点。A* 在 g(n) 基础上加入启发式估计 h(n)，用 f(n)=g(n)+h(n) 同时衡量已经走了多远和预计还要走多远，从而优先扩展更可能通向目标的节点。
图分割是什么？以 Normalized Cut 为例如何介绍？
图分割的核心是把像素、超像素或区域划分成语义或视觉一致的子区域，使同一区域内部相似度高、不同区域之间差异大。面试中不要只罗列算法名，最好选择一种方法深入讲清楚：输入如何建模、相似度如何定义、优化目标是什么、怎么求解、效果如何评估、适用边界在哪里。以 Normalized Cut 为例，它把图像表示成加权无向图，把分割转化为图划分问题，通过最小化归一化割代价，避免普通最小割偏向切出很小孤立区域的问题。
多机器人从 A 到 B，如何规划路径和调度才能效率最高？
这类问题本质不是单个机器人从起点到终点的最短路，而是多机器人路径规划与调度问题。高效方案应先明确优化目标，再把仓库抽象成栅格图或有向图，在时间维度上处理多个机器人之间的点冲突、边冲突、通道容量、死锁和动态障碍。工程上通常不会追求全局最优，而是在安全避碰的前提下，用 A* 或 Dijkstra 生成单体路径，再结合优先级规划、CBS、时间扩展图、预约表、滚动重规划等方法，在最优性、实时性和系统吞吐之间取平衡。
Dijkstra 算法和 Prim 算法有什么区别？
Dijkstra 求单源最短路径，Prim 求最小生成树；两者都可用贪心和优先队列，但目标、状态含义和边权约束不同。
风险社区检测中，Louvain 和 LPA 应该如何选择？
这道题考察图算法在风控社区检测里的取舍。回答不要只背 Louvain 和 LPA 定义，要结合风险图的边权、噪声、稳定性、可解释性和处置成本说明：高精度离线团伙发现更偏 Louvain，超大规模快速扩散或候选扩展可用 LPA。
出行派单中，给定乘客-司机候选边和权重，如何建模最大权匹配？
这道题考察出行派单如何从“乘客和司机两两配对”抽象成带约束的最大权二分图匹配。高质量回答要先定义候选边和权重，再讲一对一约束、不可匹配处理、算法选择、在线批量求解、业务护栏和效果评估，而不是只背匈牙利算法。
Spring AI Alibaba Graph 的底层原理是什么，图式编排如何表达 Agent 节点、状态流转、条件分支和工具调用？
这题考察对图式 Agent 编排的理解，重点是状态、节点、边、条件路由、工具调用、失败处理和可测试性，而不是背某个版本的 API。