知识卡片

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

深度优先完成后回溯再换分支

理解等级:中级

深度优先发现一个白色顶点时先标灰,继续递归访问尚未发现的邻居;没有白色邻居可走时标黑并返回上层,继续该父节点未走的分支。灰色表示已发现但仍在探索,不是原文所写“还未发现”。

一次从根出发只覆盖可达部分。要遍历全图,外层还需检查所有顶点,对剩余白色顶点启动新一棵搜索树,合起来是深度优先森林。02919先从1探索1、2、3、5并回溯完成,再从4开始补上未发现的部分。

可记录发现和完成的先后次序,用于后续环分析、拓扑排序等;它们是搜索事件次序/时间戳,不是每顶点被重复发现的次数。父亲在首次发现时确立,各树根无父亲;并不要求图本身原本就是森林。

200/02948外层对每个仍white的顶点调用dfs_main,覆盖孤立与不连通部分;helper开始gray、完成black并头插,实际记录颜色而非发现/完成序号。

201扩展DFS时用全局递增事件计数,在白转灰记录发现序号、灰转黑记录完成序号;这是时间/次序戳,不是每顶点发现了多次。现有DfsVertex尚无这两字段,问答仅提出扩展。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      递归地访问此顶点的所有未访问过的相邻顶点。因而,这种搜索将尽可能深地持续探索,直到无法继续为止。这种策略使得深度优先搜索在很多应用中非常有用,包括环检测以及拓扑排序(见本章的第二个例子)。 图 11-7 从顶点1开始做深度优先搜索 搜索开始前,将每个顶点涂为白色,并选择一个作为起始点。该算法按照如下

    • · 查看原书依据

      最后一个循环保证对图中所有未相连的元素完成了检索,如图11-9a中展示的一样。在dfs_main中逐个完成顶点的搜索并将其涂黑,然后插入链表ordered的头部。最后,ordered就包含完成拓扑排序后的顶点。 dfs的时间复杂度为O(V+E),这里V代表图中顶点的个数,而E代表边的个数。这是因为初

    • · 查看原书依据

      计数器,每当将顶点涂黑或涂灰时就让它自增1。当顶点涂成灰色时,记录当前计数器的值作为顶点的发现次数。当顶点涂成黑色时,记录当前计数器的值作为完成搜索的次数。在本章给出的实现中,可以为结构体DfsVertex增加两个成员来记录每个顶点的发现和完成搜索次数。 问:有向图的转置是指将该图的边反转。正式的说

    参考来源

    - 位置:《算法精解:C语言描述》第11章《搜索方法》(spine1321;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1288.html;u187-ch11-014)。 - 结论依据:187深度优先全部过程/额外信息段和02919完整六阶段图实读,发现3/5后回溯2/1与最后4顺序核对,白灰黑含义纠正。 - 原始内容:递归地访问此顶点的所有未访问过的相邻顶点。因而,这种搜索将尽可能深地持续探索,直到无法继续为止。这种策略使得深度优先搜索在很多应用中非常有用,包括环检测以及拓扑排序(见本章的第二个例子)。 图 11-7 从顶点1开始做深度优先搜索 搜索开始前,将每个顶点涂为白色,并选择一个作为起始点。该算法按照如下 - 位置:《算法精解:C语言描述》第11章《关于图的应用举例:拓扑排序》(spine1333;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1300.html;u200-ch11-014)。 - 结论依据:200/02948外层对每个仍white的顶点调用dfs_main,覆盖孤立与不连通部分;helper开始gray、完成black并头插,实际记录颜色而非发现/完成序号。 - 原始内容:最后一个循环保证对图中所有未相连的元素完成了检索,如图11-9a中展示的一样。在dfs_main中逐个完成顶点的搜索并将其涂黑,然后插入链表ordered的头部。最后,ordered就包含完成拓扑排序后的顶点。 dfs的时间复杂度为O(V+E),这里V代表图中顶点的个数,而E代表边的个数。这是因为初 - 位置:《算法精解:C语言描述》第11章《问与答》(spine1334;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1301.html;u201-ch11-014)。 - 结论依据:201扩展DFS时用全局递增事件计数,在白转灰记录发现序号、灰转黑记录完成序号;这是时间/次序戳,不是每顶点发现了多次。现有DfsVertex尚无这两字段,问答仅提出扩展。 - 原始内容:计数器,每当将顶点涂黑或涂灰时就让它自增1。当顶点涂成灰色时,记录当前计数器的值作为顶点的发现次数。当顶点涂成黑色时,记录当前计数器的值作为完成搜索的次数。在本章给出的实现中,可以为结构体DfsVertex增加两个成员来记录每个顶点的发现和完成搜索次数。 问:有向图的转置是指将该图的边反转。正式的说