知识卡片

普通读书笔记卡 · 3650.d

DFS邻接表遍历线性

理解等级:中级

邻接表版 DFS 对每个顶点恰好调用一次 DFS-VISIT,并扫描每条邻接记录一次;合计 Θ(V+E),顶点和邻接顺序可改变森林形态。

这张卡片看不懂?

已有反馈 · 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 ).