我正在阅读 CLRS (https://pd.daffodilvarsity.edu.bd/course/material/book-430/pdf_content)，并陷入了第 600 页的定理 22.5 - 广度优先搜索的正确性的证明。 作者试图证明，对于图中从源 S 可达的每个顶点 v，BFS 都设置 v.d = s(S, v)，其中 v.d 是 BFS 为 v 找到的最短距离，s(S, v) 是从 S 到 v 的最短距离。但是证明中的一个步骤假设上述属性对于 v 的某些邻居顶点 u 成立，给出的原因是“因为我们如何选择 v”。我确信我在这里遗漏了一些东西。
选择 v 的方式有什么特别之处，可以让我们对 v 的某个邻居 u 假设上述属性？
但是证明中的一个步骤假设上述属性对于 v 的某些邻居顶点 u 为真
不仅仅是𝑣的some邻居，而且是在广度优先路径上𝑣之前的邻居。引用正文：
令 𝑢 为从 𝑠 到 𝑣 的最短路径上紧邻 𝑣 之前的顶点，使得 δ(𝑠,𝑣) = δ(𝑠,𝑢) + 1。因为 δ(𝑠,𝑢) < δ(𝑠,𝑣), and because of how we chose 𝑣, we have 𝑢.𝑑 = δ(𝑠,𝑢).
“我们如何选择𝑣”指的是以下内容：
令 𝑣 为接收到不正确 𝑑 值的具有最小 δ(𝑠,𝑣) 的顶点；
这里的关键词是“最小”。这意味着比 𝑣 更接近 𝑠 的 𝑢 不可能有错误的 𝑑，否则 𝑣 就不是最小的。所以我们相信 𝑢.𝑑 是 δ(𝑠,𝑢)。