知识卡片
BFS队列距离单调且差不超一
BFS 队列中顶点按 d 非递减排列,队尾 d 最多比队头大一。这是 FIFO 与新邻点 d=u.d+1 共同维持的层次不变量;它支撑先入队顶点不会比后入队顶点更远。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第20章 基本图算法 · 查看原书依据
Lemma 20.3 Suppose that during the execution of BFS on a graph G = (V, E), the queue Q contains the vertices 〈v1, v2,
参考来源
- 位置:《算法导论(第4版)》第20章《基本图算法》(OEBPS/chapter020.xhtml,文本字符[20000,25000))。
- 结论依据:引理20.3给出队列头尾差值与相邻距离单调性。
- 原始内容:Lemma 20.3 Suppose that during the execution of BFS on a graph G = ( V , E ), the queue Q contains the vertices 〈 v 1 , v 2 , … , v r 〉 , where v 1 is the head of Q and v r is the tail. Then, v r .d ≤ v 1 . d + 1 and v i .d ≤ v i +1 . d for i = 1, 2, … , r – 1.