知识卡片

普通读书笔记卡 · 5654.c.3.f

图DFS用访问集阻止回环

理解等级:中级

DFS记录当前顶点,再选择一个未访问邻居深入,返回后继续其他邻居。visited让已经完成或正在路径上的顶点不再被递归进入,避免图中的环造成无限重复。

访问顺序依邻居顺序而不同,调用深度最坏可达顶点数。它和树DFS共享深入再回退的控制方式,但图必须额外处理多个入口和回环,不能只照树代码无限递归。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      也需要借助一个哈希表visited 来记录已被访问的顶点,以避免重复访问顶点。 // === File: graph_dfs.go === /* 深度优先遍历辅助函数 */ func dfs(g *graphAdjLis

    参考来源

    - 位置:《Hello 算法--Go版本》第09章《图》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;spine 4,归一字符[6695,6805)) - 结论依据:实际graphDFS/dfs代码与图步骤支持。 - 原始内容:也需要借助一个哈希表visited 来记录已被访问的顶点,以避免重复访问顶点。 // === File: graph_dfs.go === /* 深度优先遍历辅助函数 */ func dfs(g *graphAdjLis