知识卡片
BFS按邻接表线性遍历
BFS 中每个顶点最多入队和出队一次,每条邻接表也只在其顶点出队时扫描一次;连同初始化,时间为 O(V+E)。
这个结论依赖邻接表表示,换成矩阵需重新计算。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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 .