知识卡片

普通读书笔记卡 · 3649.d

BFS按邻接表线性遍历

理解等级:中级

BFS 中每个顶点最多入队和出队一次,每条邻接表也只在其顶点出队时扫描一次;连同初始化,时间为 O(V+E)。

这个结论依赖邻接表表示,换成矩阵需重新计算。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第20章 基本图算法 · 查看原书依据

      The overhead for initialization is O(V), and thus the total running time of the BFS procedure is O(V + E). Thus, breadth-first search runs in time linear in the size of the adjacency-list representation of G.

    参考来源

    - 位置:《算法导论(第4版)》第20章《基本图算法》(OEBPS/chapter020.xhtml,文本字符[15000,20000))。 - 结论依据:原文分别计入队列、邻接表扫描和初始化成本,得出O(V+E)。 - 原始内容:The overhead for initialization is O ( V ), and thus the total running time of the BFS procedure is O ( V + E ). Thus, breadth-first search runs in time linear in the size of the adjacency-list representation of G .