图论·单选训练3

第 1 题（单选）

0-1 BFS 适用于边权只为（）的最短路。

{{ select(1) }}

• 任意实数
• 任意非负整数
• 全部负数
• 0 和 1

第 2 题（单选）

最小生成树一定满足的性质是（）。

{{ select(2) }}

• 连接所有点且无环
• 包含图中所有边
• 边权必须不同
• 只适用于有向图

第 3 题（单选）

若图不连通，则最小生成树（）。

{{ select(3) }}

• 仍一定存在
• 边数为 m
• 不存在覆盖所有点的生成树
• 等于最短路树

第 4 题（单选）

二分图最大匹配的增广路算法中，找到一条增广路会使匹配数（）。

{{ select(4) }}

• 不变
• 减少 1
• 增加 1
• 变为 0

第 5 题（单选）

某 DAG 只有边 1→3 和 2→3。关于它的拓扑序，正确的是（）。

{{ select(5) }}

• 只有 1,2,3
• 只有 2,1,3
• 1,2,3 和 2,1,3 都是合法拓扑序
• 1,3,2 和 3,1,2 都是合法拓扑序