图论·多选训练6

第 1 题（多选）

关于最短路算法，正确的有（）。

{{ multiselect(1) }}

• Kruskal 可求任意单源最短路
• Dijkstra 标准算法要求非负边权
• 0-1 BFS 适合 0/1 边权
• Bellman-Ford 可用于检测负环

第 2 题（多选）

关于 DAG 与拓扑序，正确的有（）。

{{ multiselect(2) }}

• 拓扑排序过程也可用于发现有向环
• 有向图存在覆盖全部顶点的拓扑序当且仅当它是 DAG
• 有环时不存在完整拓扑序
• 任意无向图都有拓扑序

第 3 题（多选）

关于 LCA，正确的有（）。

{{ multiselect(3) }}

• 欧拉序 + RMQ 可求 LCA
• LCA 只在二叉树中有定义
• LCA 是最近公共祖先
• 倍增可求 LCA

第 4 题（多选）

关于可撤销并查集，正确的有（）。

{{ multiselect(4) }}

• 通常避免普通路径压缩
• 常用于离线分治动态图
• 天然支持任意在线删边且无需额外结构
• 通常记录修改栈

第 5 题（多选）

关于 0-1 BFS，正确的有（）。

{{ multiselect(5) }}

• 使用双端队列
• 适合任意负权图
• 适合边权为 0 或 1 的最短路
• 一定比 Dijkstra 适用范围更广