知识卡片
深度优先搜索沿分支回溯
从起点将未访问顶点标为灰色,沿未访问邻边递归深入;处理完所有邻边后标黑并回溯。发现与完成时间以及前驱记录了搜索森林,邻边迭代顺序会影响具体树和时间。只从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)。