知识卡片

普通读书笔记卡 · 5654.d.1.f.4.d · 生成模型:未记录

深度优先搜索沿分支回溯

理解等级:中级

从起点将未访问顶点标为灰色,沿未访问邻边递归深入;处理完所有邻边后标黑并回溯。发现与完成时间以及前驱记录了搜索森林,邻边迭代顺序会影响具体树和时间。只从s运行访问s可达顶点;若还从其余白色顶点继续,得到覆盖全图的森林。

前驱链提供搜索树中的路径,但不保证边数或权重最短;森林其他根的前驱链也不通向s。递归实现还需要 O(V) 最坏调用栈,不能只计算颜色数组。

150说明每棵DFS树根的前驱为−1;有向图的遍历森林由顶点顺序决定,树根不是无向连通分量的通用替代。输入源点须属于图。

151强调DFS仅要求可遍历邻接点;完整空间包括颜色、可选前驱和时间数组以及最坏 O(V) 的递归栈。

153在邻接表下,完整森林遍历耗时 O(V+E):无向边通常以两个邻接项出现,仍只是常数倍。若用邻接矩阵逐行扫描,成本可为 O(V²)。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 4 处

    • · 查看原书依据

      深度优先搜索 考虑图6-7左边的迷宫。在经过一些尝试后,一个孩子能够快速地找到从起点s到终点t的路。但是计算机解决这个问题看起来就比较复杂,一种方法是假设离目标并不太远,然后做尽可能多的深度移动。也就是说,只要可以,随机选择一个方向,然后向这个方向前进,标记一下起点。如果你走上一条死路,或者不能在不

    • · 查看原书依据

      深度优先森林。对于森林中的树来说,它们根节点的pred[r]的值都为-1。 假设 此算法对于有向图和无向图同样适用。 [1]注意,这里的“最短路径”指的是s到t经过的点的个数最少。

    • · 查看原书依据

      存储开销。 深度优先搜索能够在数组中存储其遍历图时的信息。事实上,深度优先搜索对图的唯一要求是能够遍历给定顶点的所有邻接顶点,于是这样,我们能够在复杂的数据结构上方便地进行深度优先搜索。因为df_visit函数将原图看做一个只读结构。但是,深度优先搜索仅仅依靠当前的信息,是一种盲目的搜索,它并没有一

    • · 查看原书依据

      O(V+E)。

    参考来源

    - 位置:《算法技术手册》第6章《深度优先搜索》(spine1566;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1529.html;u149-ch06-005)。 - 结论依据:149全文、03282–03285迷宫图、伪代码及时间表实读。 - 原始内容:深度优先搜索 考虑图6-7左边的迷宫。在经过一些尝试后,一个孩子能够快速地找到从起点s到终点t的路。但是计算机解决这个问题看起来就比较复杂,一种方法是假设离目标并不太远,然后做尽可能多的深度移动。也就是说,只要可以,随机选择一个方向,然后向这个方向前进,标记一下起点。如果你走上一条死路,或者不能在不 - 位置:《算法技术手册》第6章《输入/输出》(spine1566;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1529.html;u150-ch06-005)。 - 结论依据:150说明每棵DFS树根的前驱为−1;有向图的遍历森林由顶点顺序决定,树根不是无向连通分量的通用替代。输入源点须属于图。 - 原始内容:深度优先森林。对于森林中的树来说,它们根节点的pred[r]的值都为-1。 假设 此算法对于有向图和无向图同样适用。 [1]注意,这里的“最短路径”指的是s到t经过的点的个数最少。 - 位置:《算法技术手册》第6章《使用环境》(spine1567;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1530.html;u151-ch06-005)。 - 结论依据:151强调DFS仅要求可遍历邻接点;完整空间包括颜色、可选前驱和时间数组以及最坏 O(V) 的递归栈。 - 原始内容:存储开销。 深度优先搜索能够在数组中存储其遍历图时的信息。事实上,深度优先搜索对图的唯一要求是能够遍历给定顶点的所有邻接顶点,于是这样,我们能够在复杂的数据结构上方便地进行深度优先搜索。因为df_visit函数将原图看做一个只读结构。但是,深度优先搜索仅仅依靠当前的信息,是一种盲目的搜索,它并没有一 - 位置:《算法技术手册》第6章《分析》(spine1569;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1532.html;u153-ch06-005)。 - 结论依据:153在邻接表下,完整森林遍历耗时 O(V+E):无向边通常以两个邻接项出现,仍只是常数倍。若用邻接矩阵逐行扫描,成本可为 O(V²)。 - 原始内容:O(V+E)。