图论·多选训练8

第 1 题（多选）

关于 BFS，正确的有（）。

{{ multiselect(1) }}

• 常用队列实现
• 按层扩展
• 无权图中可求最少边数距离
• 可直接处理任意负权最短路

第 2 题（多选）

关于 DFS 与回溯，正确的有（）。

{{ multiselect(2) }}

• 修改共享状态的回溯搜索通常要撤销选择
• DFS 可递归实现
• 所有 DFS 都必须恢复状态
• 可用于连通块遍历

第 3 题（多选）

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

{{ multiselect(3) }}

• 普通并查集天然支持任意删边
• union 合并集合
• find 查询代表元
• 路径压缩可优化复杂度

第 4 题（多选）

关于二分图，正确的有（）。

{{ multiselect(4) }}

• 所有树都是二分图
• 不存在奇环是判定性质
• 所有完全图都是二分图
• 可用两色染色判定

第 5 题（多选）

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

{{ multiselect(5) }}

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