知识卡片
DFS邻接表遍历线性
邻接表版 DFS 对每个顶点恰好调用一次 DFS-VISIT,并扫描每条邻接记录一次;合计 Θ(V+E),顶点和邻接顺序可改变森林形态。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第20章 基本图算法 · 查看原书依据
The procedure DFS-VISIT is called exactly once for each vertex v ∈ V, since the vertex u on which DFS-VISIT is invoked must be white and the first thing DFS-VISIT does is paint vertex u gray. During an execution of DFS-VISIT(G, v), the loop in lines 4–7 executes |Adj[v]| times. Since Σv∈V |Adj[v]| = Θ(E) and DFS-VISIT is called once per vertex, the total cost of executing lines 4–7 of DFS-VISIT is Θ(V + E). The running time of DFS is therefore Θ(V + E).
参考来源
- 位置:《算法导论(第4版)》第20章《基本图算法》(OEBPS/chapter020.xhtml,文本字符[35000,40000))。
- 结论依据:运行时间分析证明每个顶点恰调用一次DFS-VISIT,邻接表扫描次数求和为Θ(E),连同顶点初始化得到Θ(V+E);顺序依赖见同节后文。
- 原始内容:The procedure DFS-V ISIT is called exactly once for each vertex v ∈ V , since the vertex u on which DFS-V ISIT is invoked must be white and the first thing DFS-V ISIT does is paint vertex u gray. During an execution of DFS-V ISIT ( G , v ), the loop in lines 4–7 executes | Adj [ v ]| times. Since Σ v ∈ V | Adj [ v ]| = Θ( E ) and DFS-V ISIT is called once per vertex, the total cost of executing lines 4–7 of DFS-V ISIT is Θ( V + E ). The running time of DFS is therefore Θ( V + E ).