题目

下列关于图的叙述中，正确的是( )。

错因

A

混淆了"有向图"与"DAG（有向无环图）"。在 DAG 中确实存在入度 0 的顶点（这是拓扑排序能开始的依据），但任意有向图可以含环——比如三个顶点 A→B→C→A 构成的 3-环，每个顶点入度都是 1，没有入度为 0 的点。命题加上"无环"才正确。

B

拓扑排序的存在性正确（DAG 一定能拓扑排序），但唯一性通常不成立。只有当 DAG 是一条"链状"的偏序（任意两个顶点之间有可达关系，即存在唯一的哈密顿路径）时拓扑序才唯一。一般 DAG 中互无依赖的多个顶点可以任意排序。反例：边 、 构成的两条独立链，A,B,C,D 与 A,C,B,D 都是合法拓扑序。

D

BFS 把每条边视为权值 1，沿层级扩展只能保证"边数最少"，不能保证"权和最少"。反例：A→B 权 10，A→C→B 权 1+1，BFS 会先到 B（边数少），却不是最短路。带权图的最短路径需 Dijkstra（无负权）或 Bellman-Ford（含负权）等算法。

总解析

思路：选项 C 是图论中的经典结论，证明依赖"无回路图（树或森林）必有度 = 1 的叶子"这一性质。

反向论证：

若无向图 中所有顶点度 ，假设它无回路，则 是树或森林（即所有连通分量都是树）。但任意一棵有 个顶点的树中，叶子节点的度恰为 1——这与"度 "矛盾。故 必含回路。

也可以构造性地理解：从任一顶点出发沿任意未走过的邻接边前进，每个顶点至少有一条"出口边"（度 保证至少一条邻边可走），但顶点数有限，必然在某一步重新踏上已访问的顶点，形成回路。

逐项核对：

• A ✗ 反例：3-环 A→B→C→A，所有顶点入度 1。
• B ✗ 反例：两条互不相关的边 A→B、C→D。
• C ✓ 经典结论，由"无回路 → 树 / 森林 → 必有度 1 顶点"反证得到。
• D ✗ BFS 只适用于无权图（或边权全相等）。

最终答案是 C。