判断题：所有DFS(s)生成树的叶节点v是否必为所有BFS(s)生成树叶节点(v≠s)

算力阿峰

2026-9-28

命题结论

该命题为真，以下是严谨证明：

第一步：推导前提的等价性质

已知条件：v（v≠s）在所有以s为根的DFS生成树中都是叶节点。
首先明确：节点在DFS生成树中为叶节点，当且仅当它的所有邻居都在它之前被DFS访问——如果存在任意一个邻居在它之后被访问，这个邻居就会成为它的子节点，它就不是叶节点。
因此已知条件等价于：所有以s为起点的DFS遍历中，v的全部邻居都先于v被访问。

第二步：证明v的所有邻居到s的最短距离都小于v到s的最短距离

用反证法推导：假设存在v的一个邻居u，u到s的最短距离 ≥ v到s的最短距离d。
因为u和v直接相连，所以u到s的最短距离最多是d+1，仅存在两种可能：

若u到s的最短距离等于d：可构造DFS遍历先走s到v的最短路径到达v，此时u还未被访问，接下来访问邻居u，u就会成为v的子节点，v不是叶节点，和已知条件矛盾。
若u到s的最短距离等于d+1：同样可构造DFS遍历先走s到v的最短路径到达v，此时u未被访问，访问u后u成为v的子节点，和已知条件矛盾。

因此假设不成立，v的所有邻居到s的最短距离都严格小于v到s的最短距离d。

第三步：推导BFS生成树中v必为叶节点

BFS遍历的核心性质是：节点被访问的顺序和它到s的最短距离严格正相关，所有最短距离为k的节点，一定在所有最短距离为k+1的节点之前被访问。
已知v的最短距离是d，所有邻居的最短距离都小于d，因此所有邻居都在v之前被访问。BFS生成树中，节点的子节点只能是在它之后被访问的邻居，因此v没有子节点，必然是叶节点。