《算法设计手册》BFS非树边性质来源及有向图回边证明疑问

推导的核心锚点 #

BFS算法在执行过程中为每个顶点分配的层级值d[v]，严格等价于图中从根节点到顶点v的最短路径长度，这就是“BFS树中的每条路径都是对应图的最短路径”的准确内涵。
所有非树边的性质都可以基于这个定义直接推导，不需要引入额外的约束条件。

无向图非树边性质的推导 #

无向图中所有非树边的核心约束是：边的两个端点的层级差绝对值一定不超过1，也就是非树边只能连接同层级顶点，或者相邻层级的顶点，刚好对应“非树边仅可指向与父顶点处于同一层级、或父顶点所在层级的下一层顶点”的结论，推导过程用反证法即可：

• 假设存在一条非树边连接u和v，且两个端点的层级差为2，比如d[v] ≥ d[u] +2
• 沿着根节点到u的最短路径（长度为d[u]）走完后，再通过这条非树边走到v，能得到一条长度为d[u]+1的根到v的路径
• 根据d[v]是根到v的最短路径长度的定义，必须满足d[v] ≤ d[u]+1，这和一开始假设的d[v]≥d[u]+2矛盾
• 因此层级差超过1的边在无向图BFS过程中不可能出现。由于无向图边没有方向，不存在单向指向上一层的情况——所有跨层非树边本质上都是从较低层的顶点出发，指向相邻的更高层顶点，因此从高楼层的顶点视角看，非树边只能连接同层顶点，或者自己所在层的下一层顶点。

有向图回边存在条件的证明 #

有向图的边带有方向属性，对任意有向边u→v，根据最短路径的定义，永远满足基础不等式：d[v] ≤ d[u] +1——因为沿着根到u的最短路径走到u后，通过这条边就能到达v，得到一条长度为d[u]+1的根到v的路径，因此v的最短路径长度不可能比这个值更大。
基于这个不等式，可以把所有可能的边的层级关系做分类讨论，就能推导出回边的存在条件：

1. 如果满足d[v] > d[u]+1，这种有向边从根源上就不可能存在，和BFS的规则无关
2. 剩下所有合法的有向边（包括树边、非树边）只存在三种层级关系：
   • d[v] = d[u]+1：如果u是v在BFS树中的父节点，这就是BFS树边；如果u不是v的父节点，就是从低层指向相邻高层的非树正向边
   • d[v] = d[u]：从u指向同层顶点v的非树横向边
   • d[v] < d[u]：从高层顶点u指向比自己离根更近的顶点v的边，也就是题目所说的回边。这类边作为非树边存在时，完全不会违反最短路径的定义：沿着u→v的边得到的根到v的路径长度为d[u]+1，但v本身的最短路径长度d[v]小于d[u]，自然也就不会产生更优的路径和d[v]的取值冲突。
     这也就是为什么有向图的回边没有类似无向图的相邻层限制——只要边的方向是从u指向离根更近的v，就可以作为非树回边存在，不会和BFS的最短路径性质矛盾。

内容的提问来源于stack exchange，提问作者InChul Song