知识卡片
图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