知识卡片

普通读书笔记卡 · 3649.a.1

BFS队列距离单调且差不超一

理解等级:高级

BFS 队列中顶点按 d 非递减排列,队尾 d 最多比队头大一。这是 FIFO 与新邻点 d=u.d+1 共同维持的层次不变量;它支撑先入队顶点不会比后入队顶点更远。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.