知识卡片
深度优先完成后回溯再换分支
深度优先发现一个白色顶点时先标灰,继续递归访问尚未发现的邻居;没有白色邻居可走时标黑并返回上层,继续该父节点未走的分支。灰色表示已发现但仍在探索,不是原文所写“还未发现”。
一次从根出发只覆盖可达部分。要遍历全图,外层还需检查所有顶点,对剩余白色顶点启动新一棵搜索树,合起来是深度优先森林。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增加两个成员来记录每个顶点的发现和完成搜索次数。 问:有向图的转置是指将该图的边反转。正式的说