图论·多选训练9

第 1 题（多选）

关于 Dijkstra，正确的有（）。

{{ multiselect(1) }}

• 能直接处理任意负环
• 可用优先队列优化
• 常用于单源最短路
• 标准算法要求非负边权

第 2 题（多选）

关于邻接表，正确的有（）。

{{ multiselect(2) }}

• 遍历所有边方便
• 适合稀疏图
• 任意两点查边一定 O(1)
• 空间通常 O(n^2)

第 3 题（多选）

关于邻接矩阵，正确的有（）。

{{ multiselect(3) }}

• 查询两点是否有边方便
• 无法表示有向图
• 适合点数较小或稠密图
• 空间通常 O(n+m)

第 4 题（多选）

关于图的度数，正确的有（）。

{{ multiselect(4) }}

• 无向图度数和为 m
• 有向图入度和等于出度和
• 树的度数和为 n-1
• 无向图度数和为 2m

第 5 题（多选）

关于 BFS ，正确的有（）。

{{ multiselect(5) }}

• 需记录是否访问避免重复
• 一定要用递归实现
• 每格最多入队一次时复杂度与格子数同阶
• 可直接处理带负权边